에라토스테네스의 체

가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미한다.

1. 숫자 1개가 소수인지 판별할 때

Boolean isPrimeNumber(int x) {
	for(int i = 2; i < x ; i++) {
    	if(x % i == 0) return false;
    }
}

시간복잡도는 O(N)이다. 모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 비효율적이다.

소수 판별을 하고자 하는 수의 제곱근까지만 판별해도 소수인지의 여부를 판단할 수 있다.

    boolean isPrime(int Number) {
        for(int i = 2; i <= Math.sqrt(Number); i++) {
            if(Number % i == 0) return false;
        }
        return true;
    }
    

2. 소수 판별할 수가 많을 때
   n까지의 자연수 중에서 소수인 수를 구한다면?
   2,3, ... 배수를 지운다.

public class Main {
    public static void main(String[] args) {
        primeNumberSieve();
    }
    
    static void primeNumberSieve() {
        int number = 100;
        int[] a = new int[101];

        for(int i=2; i<=number; i++) {
            a[i] = i;
        }
        for(int i=2; i<=number; i++) {
            if(a[i] == 0) continue;
            for(int j = i+i; j<=number ; j+=i) {
                a[j] = 0;
            }
        }
        for(int i=2; i<=number; i++) {
            if(a[i] != 0) System.out.println(a[i]);
        }
    }
}