[Java] 소수 구하기

▤ 목차

• 1. 소수 구하기
  • 1. 방법1 (N까지 나누기)
  • 2. 방법2 (N의 제곱근보다 작은 수까지 나누기)
  • 3. 방법3 (에라토스테네스의 체)

1. 소수 구하기

1. 방법1 (N까지 나누기)

N 보다 작은 자연수들로 나눈 후 소수인지 아닌지 판별하는 알고리즘이다. 

시간복잡도: O(N²)

public boolean isPrime(int n) {
    if (n <= 1) return false;			// 1보다 작으면 false 반환
    for (int i = 2; i < n; i++) {		// 2보다 크고 n보다 작은 수로 나눈다.
        if (n % i == 0) return false;		// 만약 나누어 떨어지는 것이 있다면 false 반환
    }
    return true;				// 모두 나누고도 떨어지는 수가 없다면 true 반환
}

2. 방법2 (N의 제곱근보다 작은 수까지 나누기)

첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 N의 제곱근(√) 까지만 나눈다.

소수인지 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문에 제곱근까지만 판별하면 된다.

만약 n=36일 때

• 1×36=36
• 2×18=36
• 3×12=36
• 4×9=36
• 6×6=36 (제곱근에서 대칭의 끝)

즉, 약수는 작은 수와 큰 수로 짝을 이루고 있으며, 그 짝 중 하나는 항상 √n​보다 작거나 같고, 다른 하나는 √n​보다 크거나 같다.

어떤 수 n이 소수가 아니라면, 최소 하나의 약수는 √n​ 이하의 범위에 존재해야 한다.

36이 소수인지 확인하려고 한다면, 1부터 √ 36=6 까지만 나누어 보면 된다.

2, 3, 4, 6 중 하나라도 나누어 떨어지면 36은 소수가 아니라고 결론 내릴 수 있다.

왜냐하면, 그 이후에 나오는 약수들은 6보다 큰 값으로, 이미 6 이하에서 발견된 약수와 대칭적으로 대응되기 때문이다.

예를 들어 12는 3에 대응하고, 18은 2에 대응한다.

만약 √n​ 이하의 값으로 나누어지지 않는다면, 그 이후의 값들로도 나누어지지 않는다.

정리하자면

1. 약수는 대칭적으로 존재한다. 예: a×b=n이면, a와 b 중 하나는 반드시 √ n​ 이하다.
2. 소수를 확인할 때는 √n​까지의 수만 나눠보면 충분하다. √n​ 이후의 수로 나누어 떨어질 수 없다면, 그 이전에도 나누어 떨어지지 않았을 것이기 때문이다.

따라서, 소수를 판별할 때는 굳이 그 수 자체까지 나눌 필요 없이 √ n​까지만 나누어도 소수인지 아닌지를 알 수 있다.

시간복잡도: O(N√N)

public boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {			// n의 제곱근까지 나누기
        if (n % i == 0) return false;
    }
    return true;
}

3. 방법3 (에라토스테네스의 체)

i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식

먼저 가장 작은 수인 2를 소수로 등록한 후, 2의 배수를 지운다. -> 지우지 않은 수 중 가장 작은 수인 3을 소수로 등록한 후, 3의 배수를 지운다. -> 이를 계속 반복하여 남은 수가 소수이다.

시간복잡도: O(Nlog(log N))

public boolean[] sieveOfEratosthenes(int n) {

    //0부터 n까지의 수이기 때문에 n+1을 할당한다.
    boolean[] prime = new boolean[n+1];
    
    // 0과 1은 소수가 아니기 때문에 false를 저장한다.
    prime[0] = false;				
    prime[1] = false;
    
    // n의 제곱근까지 나눈다.
    for(int i = 2; i <= Math.sqrt(n); i++) {
        
        	// 소수라면 뒤에 오는 코드를 스킵한다.
		if(prime[i] == true) {
			continue;
		}
        
		// 2부터 배수에 해당하는 수를 true로 변환한다.
		for(int j = i * i; j < prime.length; j = j+i) {
			prime[j] = true;
        	}
	}
    return prime;
}

https://sfida.tistory.com/28

[Algorithm] JAVA 소수판별 - 에라토스테네스의 체

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.