에라토스테네스의 체

에라토스테네스의 체

에라토스테네스의 체는 합성수를 지우는 방식으로 소수를 찾는 방법이다.

소수(Prime Number)

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 약수로 1과 자기 자신만을 가지는 정수라고 할 수 있다.

합성수

1과 자기 자신 이외의 약수를 가진 정수로 두개 이상의 소수의 곱이다.(비소수)

동작 과정

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 수 중 제일 작은 5를 소수로 채택하고 나머지 5의 배수를 모두 지운다.
5. 이러한 과정을 반복한다.

코드(Python)

n = int(input())
a = [False, False] + [True]*(n-1)
primes =[]
​
for i in range(2, n+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            a[j] = False
print(primes)

- 입력한 n 값 까지의 모든 소수를 구하는 코드이다.

- [False, False]를 해주는 이유는 인덱스의 시작은 0이기 때문에 0과 소수가 아닌 1을 False로 해준다.

- for j in range(2*i, n+1, i)는 동작과정 2 ~ 5 과정을 해주는 것이다.

참고 : https://wikidocs.net/21638

코드(Java)

import java.util.ArrayList;
import java.util.Scanner;
 
public class Eratostenes {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        boolean[] primeList = new boolean[n+1];
        ArrayList<Integer> prime = new ArrayList<Integer>();
        
        primeList[0] = false;
        primeList[1] = false;
        
        for(int i =2; i<=n; i++) {
            primeList[i] = true;
        }
        
        for(int i=2; i<n+1; i++) {
            if(primeList[i]) {
                prime.add(i);
                for(int j=2*i; j<=n; j+=i) {
                    primeList[j] = false;
                }
            }
        }
        
        System.out.println(prime);
        
    }
 
}