[수학] 소수 구하기

소수 판별 알고리즘

 

1. 1과 자기 자신을 제외한 나머지 수 중에서 약수가 있는  -> 시간 복잡도 O(n) 

1을 제외한 2부터 n-1까지 탐색하면서 i로 나누어 떨어지는 수가 있는지 확인

static boolean isPrime(int N) {
    if (N < 2) return false;
    for (int i=2; i<=N-1; i++) {
    	if (N/i == 0) return false;
    }
    return true;
}

 

 

2. 제곱근을 이용한 방식 -> 시간 복잡도 : O(루트 n)

만약 N이 12라 할때, 12의 제곱근은 약 3.46이다. 12의 약수는 1, 2, 3, 4, 6, 12 이다.
여기서 1과 12를 제외했을 때 이는 2 * 6, 3 * 4, 4 * 3, 6 * 2의 결과이다.

따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다.

static boolean prime(int n) {
        if(n < 2) return false;

        for(int i = 2; i * i <= n; i++) {
            System.out.print(i + " ");
            if(n % i == 0) return false;
        }
        return true;
    }

 

 

3. 에라토스테네스의 체 => 시간 복잡도 : O(n log(logn))

1. 소수가 아닌 1을 지운다.

 

2. 1을 더하여 2(소수)를 남겨두고 2의 배수를 모두 지운다.

 

3. 1을 증가시켜서 3(소수)을 남겨두고(지워지지 않음), 3의 배수를 모두 지운다.

 

4. 1을 증가시켜서 4는 2의 배수로 인해 모두 지워졌으므로 넘어간다. (=소수가 아니다)

 

즉, 2부터 N-1까지 1씩 증가시키면서 선택된 수(=소수)는 남겨두고, 선택된 수의 배수를 모두 지우는 것(=약수가 존재하므로 소수가 아니다)을 반복한다.

 

5. 더 이상 지울 수가 없다면 종료, 남겨진 수들은 모두 소수이다.

 

위키피디아

 

package algorithms.Math.PrimeNumber;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] check = new boolean[m+1];
        check[0] = check[1] = true;
        for(int i=2; i*i <= m; i++) {
            if(check[i]) {
                continue;
            }
            for(int j=i+i; j <= m; j+=i) { // 해당하는 수는 소수. 소수의 배수부터 지워준다.
                check[j] = true;
            }
        }
        for(int i = n; i <= m; i++) {
            if(!check[i]) System.out.println(i);
        }
    }
}