효율적인 소수 판별법

이미 알고 있는 소수 판별법

이미 알고 있는 소수 판별법은 다음 두 가지 방법이었다.

 

문제 : 자연수 X이 소수인가?

• 반복문을 이용하여 자연수 X을 2 ~ X-1까지 나눠봐서 한 번이라도 나머지가 0인 경우가 나오면 자연수 X은 소수가
  아니다.
• 약수는 쌍을 이룬다는 점을 이용하여 2 ~ X-1까지가 아닌 2 ~ X/2까지 나눠봐서 자연수 X이 소수인지 판별할 수 있다.

 

하지만, 2 ~ root(X)이하까지만 나눠봐도 해당 숫자가 소수인지를 효율적으로 판별할 수 있다고 한다.  

직감적으로 "왜 root(X) 이하까지만 나눠도 되는가?"를 이해할 수 없어 수식적으로 증명해 보자 한다.

 

 

왜 root(X) 이하까지만 나눠도 되는가?

가정 : 자연수 X은 소수가 아닌 합성수이며, 자연수 X은  M * N으로 표현할 수 있다. 

          (이때, M >= N이라고 하자.)

 

M과 N의 관계식에 의해서 다음 식이 성립된다.

• M * M >= M * N
• M^2 >=  X
• root(M^2) >= sqrt(X)
• M >= sqrt(X) >= N

위 과정을 통해 알 수 있듯이 약수 M은 sqrt(X)보다 크거나 같으며, 약수 N은 sqrt(X)보다 같거나 작다는 관계식을 얻는다.

이를 통해 "자연수 X가 합성수라면 반드시 sqrt(X)보다 작은 약수를 갖는다."는 것을 알 수 있으며, 이를 이용하여 root(X)까지만 생각하여 해당 자연수가 소수인지를 판단할 수 있다.

 

public class programming {
	public static void main(String[] args) {
		int N = 97;
		boolean isPrime = true;

		for(int i=2; i<Math.pow(N, 0.5) && isPrime; i++)
			if(N%i==0)
				isPrime = false;

		if(isPrime)
			System.out.println(N);
	}
}

위 코드는 97이 소수인지 판별하는 코드이며, 2 ~ sqrt(97) 범위내에서 나눠떨어지는지를 확인하였다. 

Math 라이브러리를 사용하지 않고, 아래와 같이 표현할 수도 있다.

public class programming {
	public static void main(String[] args) {
		int N = 97;
		boolean isPrime = true;

		for(int i=2; i*i<N && isPrime; i++)
			if(N%i==0)
				isPrime = false;

		if(isPrime)
			System.out.println(N);
	}
}

 

 

에라토스테네스의 체

만약 한 두개의 소수를 판별하는 것이 아닌 여러 개의 숫자들이 소수인지를 판별하기 위해서 사용하는 것이 에라토스테네스의 체이다. 에라토스테네스의 체는 1) 먼저 소수인지 판별할 숫자들을 배열형태로 만들어주고, 2) 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 제거하며 범위내에 존재하는 소수를 찾는 방식이다. 

 

영상 참고) https://www.youtube.com/watchv=5ypkoEgFdH8&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98

 

public class programming {
	public static void main(String[] args) {
		// 1 ~ 25사이에서 소수 찾기
		int[] numbers = new int[25];
		
		// 초기화
		for(int i=2; i<25; i++)
			numbers[i] = i;
		
		// 에라토스테네스의 체
		for(int i=1; i<25; i++) {
			// 삭제된 원소면 무시
			if(numbers[i] == 0)
				continue;
			// 삭제되지 않은 원소면 배수 삭제
			for(int j=i+i; j<25; j+=i)
				numbers[j] = 0;
		}
		
		for(int i=0; i<25; i++)
			if(numbers[i]!=0)
				System.out.printf("%d ", numbers[i]);
	}
}