[백준+프로그래머스] 1978번 소수 찾기 + 프로그래머스 소수 찾기

소수 찾기는 간단한 것 같으면서도 헷갈리는 그러한 문제다.

원리는 간단하다.

주어진 수의 개수를 입력받고, 주어진 수를 1~주어진 수 까지 나누어서

소수의 성질인 1과 자기자신만 나눠지는 2가지만 체크해서 결과에 ++해준다.

요즘 들어 프로그래머스의 level1 문제를 다시 풀어보고 있다.

한번 푼다고 해서 정확하게 아는것이 아니기 때문이다.

일반적인 소수찾기 문제는 어렵지 않게 풀 수 있다. 그런데 제출했더니 시간초과가 발생했다.

그래서 에라토스테네스의 체를 써야 하나보다 하고 적용하려했더니 잘 기억이 나지 않았다.

다시 풀어보길 잘한 것 같다.

에라토스테네스의 체

쉽게 말해서 2를 예로 들면 2는 소수 이지만 2의 배수인 4, 6, 8, 10 ~ 은 소수가 아니다.

3은 소수이지만 6, 9, 12, 15는 소수가 아니다. 이러한 성질을 이용해서

제곱근의 개념을 사용해 연산과정을 최소화로 줄이는 과정이다.

/*소수 찾기
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n  result
10 4
5  3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환*/
public class FindDecimal {
    public int solution(int n){
        //2, 3, 4, 5, 6, 7, 8, 9, 10

        //처음에 푼 기본적인 소수 찾기 방식
        /*boolean flag;
        int answer=0;
        for(int i=2; i<=n; i++){
            flag = true;
            for(int j=2; j<i; j++){
                if(i%j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag == true){
                answer ++;
            }

        }
        return answer;*/



        //시간초과로 인해 에라토스테네스의 체로 다시 푼 소수 찾기
        boolean flag;
        int answer=0;

        for(int i=2; i<=n; i++){
            flag = true;
            for(int j=2; j<=(int)Math.sqrt(i); j++){
                if(i%j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag == true){
                answer ++;
            }

        }
        return answer;

    }

    public static void main(String[] args) {
        FindDecimal f = new FindDecimal();
        int n = 10;
        System.out.println(f.solution(n));
    }
}