[Algorithm][Java] 소수를 나열하는 알고리즘, 소수인지 판단하기

 

 

 

 

정수 n에 대하여 아래의 조건을 만족시키면 소수임을 알 수 있다.

 

 

 

 

2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는다.

 

 

 

 

 

 

 

먼저 어떤 정수 이하의 소수를 모두 나열하는 알고리즘을 직관적으로 풀어보자.

 

 

 

public class PrimeNumber {
	public static void main(String[] args) {
		int counter=0;
		
		for(int n = 2; n <= 1000; n++) {
			int i;
			for(i = 2; i < n; i++) {
				counter++;
				if(n % i == 0)
					break;
			}
			if(n == i)
				System.out.println(n);
		}
		
		System.out.println("나눗셈을 수행한 횟수 : " + counter);
	}

}

 

 

 

소수의 정의인 2~n-1까지의 정수로 나누어지는지 일일히 확인하는 코드이다.

 

 

counter로 나눗셈을 몇번 수행하는지 확인한다.

 

 

 

실행 결과

 

 

 

실행 결과 2~1000 사이의 소수를 찾기 위해 78022번의 나눗셈이 행해진다.

 

 

 

이제 이 알고리즘을 개선해보자.

 

 

 

 

 

알고리즘 개선 (1)

 - n이 합성수인 경우 for문을 중단시킨다.

 - 소수는 2부터 n-1까지의 어떤 소수로도 나누어떨어지지 않는다.

 

 

 

 

 

 

n이 2 또는 3으로 나누어떨어지지 않으면 2x2인 4 또는 2x3인 6으로도 나누어떨어지지 않는다.

 

 

 

무슨말이냐면 위 프로그램에서 n = 13일 때 나누는 수는 다음과 같다.

 

 

 

n=13일 때

 

 

여기서 13은 2로 나누어지지 않으므로 당연히 4,6,8,10,12로도 나누어지지 않는다.

 

3으로도 나누어지지 않으므로 6,9로도 나누어지지 않는다.

 

 

 

이런식으로 하다보면 나눗셈을 11번이나 할 이유가 없는 것이다.

 

 

따라서 소수를 찾는 조건을 다음과 같이 수정할 수 있다.

 

 

 

 

2부터 n-1까지의 어떤 소수로도 나누어지지 않는다.

 

 

 

 

 

 

 

알고리즘을 개선한 코드는 다음과 같다.

 

 

public class PrimeNumber {
	public static void main(String[] args) {
		int counter = 0;
		int ptr = 0;
		int[] prime = new int[500];   // 소수를 넣어줄 배열
		
		prime[ptr++] = 2;  // prime[0] = 2를 미리 넣어준다.
		
		for(int n = 3; n <= 1000; n += 2) { // 짝수는 소수가 될 수 없으므로 홀수만
			int i;
			
			for(i = 1; i < ptr; i++) {
				counter++;
				if(n % prime[i] == 0)    // 나누어지면 소수가 아니므로 break
					break;
			}
			
			if(ptr == i)
				prime[ptr++] = n;   
			// ptr = i가 될 때까지 나누어지지 않으면 소수이므로 배열에 넣어준다.
		}
		
		for(int i = 0; i < ptr; i++)
			System.out.println(prime[i]);
		
		System.out.println("나눗셈을 수행한 횟수 : " + counter);
	}

}

 

 

 

 

소수를 저장하는 배열 prime를 만들어 그 안에 있는 소수와 n값의 나눗셈을 시도한다.

 

 

소수로 판단되면 prime 배열에 넣어주고 반복한다.

 

 

 

실행 결과

 

 

 

코드 실행 결과 78022 -> 14622

 

 

 

 

 

 

알고리즘 개선 (2)

 - 정수 n이 소수의 제곱근 이하일 때

 

 

 

 

100의 약수를 그림으로 나타내면 다음과 같다.

 

 

 

100의 약수로 직사각형 만들기

 

 

 

 

1~4번 범위에서만 나눗셈하면 된다.

 

 

 

그림에서 나타내는 넓이가 100인 직사각형들 중 1~3번과 5~7번은 같은 직사각형이다.

 

 

그러니까 10 x 10 = 100이다.

10보다 큰 수와 y값을 곱해서 100이 될 수 없다. 무조건 y < 10이 된다.

10보다 작은 값으로 소수임을 검사했을 때 소수이면 소수이고 합성수이면 합성수가 된다.

 

 

 

그러므로 100의 제곱근 값인 10보다 작은 소수와 나누었을 때 나누어지지 않는다면 소수라고 할 수 있다.

 

 

따라서 소수를 찾는 조건을 다시 한번 수정할 수 있다.

 

 

 

 

n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.

 

 

 

 

 

n의 제곱근을 계산하는 것보다 prime[]의 제곱을 계산하는 것이 더 쉬우므로 이것을 사용할 것이다.

 

 

 

알고리즘을 개선한 코드는 다음과 같다.

 

 

public class PrimeNumber {
	public static void main(String[] args) {
		int counter = 0;
		int ptr = 0;
		int[] prime = new int[500];   // 소수를 넣어줄 배열
		
		prime[ptr++] = 2;  // prime[0] = 2를 미리 넣어준다.
		prime[ptr++] = 3;  // prime[1] = 3을 미리 넣어준다.
		
		for(int n = 5; n <= 1000; n += 2) {  // 홀수만
			boolean flag = false;
			for(int i = 1; prime[i] * prime[i] <= n; i++) {
				counter += 2;   // 곱셈과 나눗셈 2번의 연산을 하므로 +2 해준다.
				
				if(n % prime[i] == 0) {  // 나누어지면 소수가 아니다. flag = true
					flag = true;
					break;
				}
			}
			
			if(!flag) {   // flag = false이면 소수이므로 prime[]에 넣어준다.
				prime[ptr++] = n;
				counter++;
			}
		}
		
		for(int i = 0; i < ptr; i++)
			System.out.println(prime[i]);
		
		System.out.println("곱셈과 나눗셈을 수행한 횟수 : " + counter);
	}

}

 

 

 

 

중간에 counter += 2; 인 이유는

 

 

곱셈 prime[i] * prime[i] 와 나눗셈 n % prime[i] 두 연산의 수행 횟수를 계산하기 위해서이다.

 

 

prime[i] * prime[i] <= n 이 성립하지 않는 경우 n % prime[i]를 수행하지 않으므로 counter는 +1만 해준다.

 

 

 

 

 

실행 결과

 

 

 

 

코드 실행 결과 78022 -> 14622 -> 3774 로 수행 횟수가 확연히 줄어든 것을 볼 수 있다.