소수 판정법

소수

소수란 1과 자기 자신 만을 약수로 갖는 수

단순한 소수 판정법

정수 N이 주어질 때, 2부터 N-1까지의 자연수 중 나누어 떨어지지 않는 수인지 확인을 하면 N이 소수라는 것을 판정할 수 있다.

위 방법을 간단하게 코드로 구현을 해보겠다.

static boolean isPrime(long N) {
	// 2 이상의 정수 N을 매개변수로 받고, N이 소수라면 True
	// 아니라면 False를 리턴하
	for (long i = 2; i <= N - 1; i++) {
		if (N % i == 0) {
			return false;
		}
	}
	return true;
}

하지만 'N'에 대하여 모든 정수 'i'에 대해 2부터 'N-1' 까지의 셈을 진행하기 때문에 'N'의 크기가 증가하면 해당 소수 판정 수행에 걸리는 시간이 많이 걸리기 때문에 효율성 부분에서는 좋다고 말을 할 수 없다.

빠른 소수 판정

앞에서 해결한 방법에서 사실 2부터 'N-1'까지 모두 확인을 할 필요는 없다.
$\sqrt{N}$ 까지만 나누어보면 소수인지 아닌지 판정할 수 있다.
반대로 이야기를 하면 모든 합성수는 2이상 $\sqrt{n}$ 이하의 정수로 반드시 나누어진다.

예를 들어 $\sqrt{43}$는 6와 7사이에 위치한다. 그래서 2부터 6까지의 수로 나누어 봤을 때 43은 소수이다.
다음으로 $\sqrt{77}$도 확인을 해보면 2부터 8까지의 수로 나누었을 때 7로 나누어진다. 그래서 77은 합성수이다.

	static boolean isPrime(long N) {
		for (long i = 2; i * i <= N; i++) {
			if (N % i == 0) {
				return false;
			}
		}
		return true;
	}