N 이하의 소수 찾기

먼저 소수란 1과 자기 자신만을 약수로 가지는 수이다. N 이하의 모든 소수를 나열하기 위해서는 정수 n이 소수인지 판별하는 법을 알아야 한다. n이 소수인지 판별하는 알고리즘과 N 이하의 모든 소수를 나열하는 알고리즘을 설명하며 단계별로 어떻게 알고리즘이 개선되는지 설명한다. 예시 코드에서 사용되는 변수 count는 계산 횟수를 저장하는 변수이다. 알고리즘의 성능을 보여주기 위해 사용한다.

방법 1

정수 n이 1과 자기 자신만을 약수로 가진다는 말은 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다는 의미이다. 이를 활용해서 정수 n이 소수인지 판별할 수 있다. 즉, 정수 n이 소수라면 2 이상 n-1 이하의 어떤 정수로도 나누어 떨어지지 않는다.

public class PrimeNumber {
	static void getPrimesVersion1(int N) {
		int count = 0;
		for (int n = 2; n <= N; n++) {
			int i;
			for (i = 2; i < n; i++) {
				count++;
				if (n%i == 0) {
					break;
				}
			}
			if (i == n) {
				System.out.print(n + " ");
			}
		}
		System.out.println("\r\n" + "계산 횟수 : " + count);
	}
}

public class App {
	public static void main(String[] args) {
		PrimeNumber.getPrimesVersion1(100);
	}
}
/* 실행결과
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
    계산 횟수 : 1133
*/

안쪽 for문에서 정수 n이 소수인지 판별하기 위해 2부터 n-1까지의 정수(i)로 나눈다. 이 과정에서 나누어 떨어진다면 소수가 아니므로 반복을 중단한다. 그러나 반복문이 끝까지 실행된다면 i값은 n과 일치하게 되므로 n은 소수임이 판별된다. 이처럼 정수 n이 소수인지 판별하는 알고리즘은 2 이상 n 미만의 자연수를 모두 검사하므로 시간 복잡도는 O($n$)이다.

바깥쪽 for문은 정수 N 이하의 모든 소수를 나열하는 알고리즘이다. 정수 n이 소수인지 판별하는 알고리즘을 N번 반복한다. 즉, 시간 복잡도가 O$(n)$인 알고리즘을 n번 반복하므로 정수 N 이하의 모든 소수를 나열하는 알고리즘의 시간 복잡도는 O$(n^2)$이다.

[시간 복잡도]
n이 소수인지 판별 : O$(n)$
N 이하의 모든 소수를 나열 : O$(n^2)$

방법 2

그런데 정수 n이 2 또는 3으로 나누어 떨어지지 않으면 2 또는 3의 배수로도 나누어 떨어지지 않는다. 2와 3으로 나누어 떨어지는지 검사했다면 2와 3의 배수들은 검사할 필요가 없다는 의미다. 그렇다면 나눠봐야 할 수는 2와 3, 그리고 나머지 수들이다. 이 수들은 소수이다. 즉, 정수 n이 소수라면 2 이상 n-1 이하의 어떤 소수로도 나누어 떨어지지 않는다.

public class PrimeNumber {
	static void getPrimesVersion2(int N) {
		int count = 0;
		int pointer = 0;
		int length = 1;
		int[] primesArray = new int[N/2];
		primesArray[pointer++] = 2;
		
		for (int n = 3; n <= N; n += 2) {
			int i;
			for (i = 0; i < pointer; i++) {
				count++;
				if (n%primesArray[i] == 0) {
					break;
				}
			}
			if (i == pointer) {
				primesArray[pointer++] = n;
				length++;
			}
		}
		
		primesArray = Arrays.copyOf(primesArray, length);
		for (int prime : primesArray) {
			System.out.print(prime + " ");
		}
		System.out.println("\r\n" + "계산 횟수 : " + count);
	}
}

public class App {
	public static void main(String[] args) {
		PrimeNumber.getPrimesVersion2(100);
	}
}
/*실행결과
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
    계산 횟수 : 362
*/

앞서 언급했듯이 n이 소수인지를 판별하기 위해서는 n을 n-1까지의 소수로 나눠봐야 한다. 이를 위해 n-1까지의 소수를 저장하는 배열 primesArray를 선언하고 2를 우선 저장한다.

방법 1과 같이 안쪽 for문에서 n이 소수인지 판별한다. 개선된 점은 n-1 이하의 '소수'로 나누고 n이 소수라면 배열 primesArray에 저장한다는 것이다. 안쪽 for문은 최악의 경우 N/2번 반복하므로 N에 비례한다. 따라서 시간 복잡도는 O((n))이다.

바깥쪽 for문에서 개선된 점은 N 이하의 모든 수가 아니라 홀수만 조사한다. 모든 소수는 홀수이기 때문이다. 또한 안쪽 for문이 종료되고 n이 소수로 판별되면 n값을 배열 primesArray에 저장한다. N 이하의 모든 소수들을 조사하는 알고리즘이 종료된 후, 저장된 소수들을 모두 출력하기 위함이다. 시간 복잡도는 방법 1과 마찬가지로 O$(n)$인 알고리즘을 n번 반복하므로 O$(n^2)$이다.

[시간 복잡도]
n이 소수인지 판별 : O$(n)$
N 이하의 모든 소수를 나열 : O$(n^2)$

방법 3

이번에는 n의 제곱근 이하의 소수로 나누어 판별한다. 그 이유는 정수 n의 약수들은 대칭성을 갖기 때문이다. 예를 들어 넓이가 100인 직사각형이라면 2*50, 4*25, 5*20, 10*10, 20*5, 25*4, 50*2의 가로, 세로 길이를 갖는 직사각형을 만들 수 있다. 100의 제곱근인 10을 한 변으로 하는 정사각형을 기준으로 대칭형태를 이루고 있다. 100이 4로 나누어 떨어지지 않는다면 25로도 나누어 떨어지지 않으므로 10*10 이후의 계산에 대해서는 고려할 필요가 없다. 즉, 정수 n이 소수라면 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

public class PrimeNumber {
	static void getPrimesVersion3(int N) {
		int count = 0;
		int pointer = 0;
		int length = 1;
		int[] primesArray = new int[N/2];
		primesArray[pointer++] = 2;
		
		for (int n = 3; n <= N; n += 2) {
			boolean flag = true;
			for (int i = 0; primesArray[i] <= Math.sqrt(n); i++) {
				count += 2;
				if (n%primesArray[i] == 0) {
					flag = false;
					break;
				}
			}
			if (flag) {
				count++;
				length++;
				primesArray[pointer++] = n;
			}
		}
		
		primesArray = Arrays.copyOf(primesArray, length);
		for (int prime : primesArray) {
			System.out.print(prime + " ");
		}
		System.out.println("\r\n" + "계산 횟수 : " + count);		
	}
}

public class App {
	public static void main(String[] args) {
		PrimeNumber.getPrimesVersion3(100);
	}
}
/*실행결과
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
    계산 횟수 : 288
*/

n이 소수인지 판별하는 하기위해 나눠봐야 할 소수의 양은 방법 2에 비해 거의 절반이 줄어든 셈이다. 이전과 달리 안쪽 for문이 모든 반복을 끝낸 후, 소수임이 판별되었을 때 변수 pointer를 이용해 정수 n을 배열에 저장할 수 없으므로 boolean 값을 저장하는 변수 flag를 사용한다. n을 n 제곱근 이하의 소수로 나누었을 때 나누어 떨어지면 flag는 false가 되어 배열에 저장되지 않는다.

안쪽 for문의 count += 2; 는 n의 제곱근과 n%primeArrays [i]에 대한 연산 횟수를 저장하기 위함이다. 그런데 안쪽 for문의 primesArray[i] <= Math.sqrt(n); 조건식이 성립하지 않는 경우 이 연산이 count에 저장되지 않는다. 그래서 for문 종료 후 등장하는 if문에서 그 횟수를 포함한다.

n이 소수인지 판별하는 안쪽 for문은 n 제곱근 이하의 수들을 검사하므로 시간 복잡도는 O$( \sqrt{n})$ 이다. 바깥쪽 for문은 안쪽 for문을 최대 N번 반복하므로 O$(\sqrt{n}*n)$ $\approx$  O$(n)$ 이다.

[시간 복잡도]
n이 소수인지 판별 : O$(\sqrt{n})$
N 이하의 모든 소수를 나열 : O$(\sqrt{n}*n)$ $\approx$  O$(n)$

저작자표시 (새창열림)

'CS > Algorithm' 카테고리의 다른 글

[Algorithm] 검색 알고리즘 : 이진 검색 알고리즘  (0) 2023.05.25

+ Recent posts

티스토리툴바