에라토스테네스의 체

소수를 구할 때 가장 잘 알려진 알고리즘이 에라토스테네스의 체

유튜브에 치면 그 원리가 자세히 나와있다

간단하게 보자면, 위의 표에서 소수인 2, 3, 5, 7, 11... 들의 배수를 하나하나 지우면서 소수가 아닌 수를 거르는 과정이다

1000000까지 어떤 수가 소수인지 확인하는 코드는 다음과 같다

1 2 3 4 5 6 7 8 9 10 11 12 13

public static boolean prime[] = new boolean[1_000_001];          //에라토스테네스의 체: false->소수     public static void get_prime() {         prime[0] = true;         prime[1] = true;                  for(int i = 2; i < Math.sqrt(prime.length); i++) {    //2부터 구하려는 숫자 범위의 제곱근까지 구한다             for(int j = i*i; j < prime.length; j += i) { // i의 제곱이라면 -> i*(i보다 작은 수)는 앞선 반복문에서 모두 사라졌을 것이므로 -> 소수가 아니다                  prime[j] = true;             }         }     } Colored by Color Scripter

cs

첫 번째 반복문에서 제곱근까지만 구하는 경우는 쉽게 생각해볼 수 있다

그림처럼, 소수가 아닌 수의 약수들은 대칭성을 가진다

따라서 2부터 구하려는 수의 제곱근까지 구해봤을 때 약수가 없다면 이 숫자는 소수라고 판별할 수 있는 것이다