에라토스테네스의 체

소수를 구하는 알고리즘

O(N log (log N)) 시간복잡도를 가진다.

 

1~100까지의 소수를 구한다면

 

1. 루트 100을 계산 : 10

2. 2부터 10까지의 수들을 차례로 순회

- 2부터 100까지 수들 중 2의 배수를 모두 제거

- 3부터 100까지의 수들 중 3의 배수를 모두 제거

...

- 10부터 100까지의 수들 중 10의 배수를 모두 제거

=> 남은 수들이 모두 소수이다.

 

1부터 N까지의 수들 중 소수를 찾는 에라토스테네스의 체 알고리즘

static List<Integer> findPrimes(int N){
    List<Integer> primes = new ArrayList<>();

    //소수인지 판별할 배열
    boolean[] isPrime = new boolean[N+1];

    //먼저 모든 수들을 true로 초기화
    for(int i=0; i<isPrime.length; i++) isPrime[i] = true;

    //0, 1은 소수가 아니다.
    isPrime[0] = isPrime[1] = false;

    //소수가 아닌 수들은 모두 false로 변경
    for(int i=2; i<=Math.sqrt(N); i++)
        for(int j=i * i; j<=N; j+=i)
            isPrime[j] = false;

    //소수인 수들을 리스트에 담아 리턴
    for(int i=0; i<isPrime.length; i++)
        if(isPrime[i]) primes.add(i);

    return primes;
}