에라토스테네스의 체

- 특정 범위 내의 소수를 찾을 때 사용하는 방법이다.

 

 

1. 1부터 N까지의 배열을 만든다. -> ex. int[] arr = {0,0,0,0,0,0,.....};

2. 소수가 아닌 1은 제거한다.

3. N까지 반복문을 돌려주면서 int[i] = 0인 값들에서 count++ 해준다.

- 2에서 count++; 

- 2의 배수는 모두 값을 1로 바꿔준다.

 

- 3에서 count++;

- 3의 배수는 모두 값을 1로 바꿔준다.

 

- 4의 배수는 2의 배수를 1로 바꿔주는 과정에서 바뀌었기 때문에 넘어간다.

....

- 마지막에 count를 출력해주면 그 값이 1부터 N까지의 소수 개수

 

 

에라토스테네스 체 사용

public static int solution(int n){
    int count = 0;
    int[] check = new int[n+1];

    for(int i=2; i<=n; i++){
        if(check[i]==0){
            count++;
            // i의 (j+i)배수들을 체크해준다.
            for(int j=i; j<=n; j=j+i){
                check[j] = 1;
            }
        }
    }

    return count;
}

 

 

소수 판별 코드

public static boolean isPrime(int num){
    if(num==1) return false; // 1은 소수가 아니다.
    for(int i=2; i<num; i++){
        if(num%i==0){ // i는 num의 약수가 된다.
            return false;
        }
    }
    return true;
}

+ Recent posts