[ALGORITHM] 소수의 나열

 

소수의 나열

소수는 자신과 1 이외의 정수로 나누어떨어지지 않는 정수 ex) 1,3,5.....

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

package ch2;

public class PrimeNumber1 {
	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);

	}

}

실행결과 ->

n이 2 또는 3으로 나누어떨어지지 않으면 2x2인 4 또은 2x3인 6으로도 나누어떨어지지 않는다. 즉 불필요한 나눗셈을 하는중.

그렇다면 n이 소수인지는 n보다 작은 소수로만 나누어보면 계산 시간을 줄일 수 있다.

---

## 알고리즘 개선(1)

1. 소수를 구하는 과정에서 그때까지 구한 소수를 배열 prime의 요소로 저장.
2. 이때 n이 소수인지 아닌지 판단하기 위해서는 쌓아두었던 소수에서 나눗셈을 진행.
3. 3이상의 소수는 이중 for문으로 구한다. n의 값을 2씩 증가하여 홀수 값만 생성. 4이상의 짝수는 2로 나누어떨어지므로 소수가 아니기 때문.

package ch2;

public class PrimeNumber2 {
	public static void main(String[] args) {
		int counter = 0;				//나눗셈의 횟수
		int ptr = 0;					//찾은 소수의 개수
		int[] prime = new int[500];		//소수를 저장하는 배열
		
		prime[ptr++]=2;					//2는 소수임
		
		for(int n=3; n<=1000; n+=2) {	//대상은 홀수만
			int i;
			for(i=1; i<ptr; i++) {		//이미 찾은 소수로 나누어 봄
				counter++;
				if(n%prime[i] ==0)		//나누어 떨어지면 소수가 아님
					break;
			}
			if(ptr == i)				//마지막까지 나누어 떨어지지 않음
				prime[ptr++] = n;		//소수라고 배열에 저장
		}
		
		for(int i=0; i<ptr; i++)		//찾은 ptr개의 소수를 나타냄
			System.out.println(prime[i]);
		
		System.out.println("나눗셈을 수행한 횟수 : " + counter);
	}
}

실행결과 ->

나눗셈을 수행하는 횟수가 현저히 감소했다.

- 결론을 내리자면
1. 같은 답을 얻는 알고리즘은 하나가 아니다.
2. 빠른 알고리즘은 메모리를 많이 요구한다.

---

알고리즘 개선(2)

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

prime[i]의 제곱근이 n이하인가?

이때 n의 제좁근을 구하는 것보다 제곱을 구하는 것이 훨씬 수월함.

package ch2;

public class PrimeNumber3 {
	public static void main(String[] args) {
		int counter = 0;					//곱셈과 나눗셈의 횟수
		int ptr = 0;						//찾은 소수의 개수
		int[] prime = new int[500];			//소수를 저장하는 배열
		
		prime[ptr++] = 2;					//2는 소수임
		prime[ptr++] = 3;					//3은 소수임
		
		for(int n=5; n<=1000; n+=2) {		//대상은 홀수만
			boolean flag = false;
			for(int i =1; prime[i]*prime[i] <=n; i++) {
				counter +=2;
				if(n%prime[i]==0) {			//나누어떨어지면 소수가 아님
					flag = true;
					break;					//더 이상의 반복은 불필요
				}
			}
			if(!flag) {						//마지막까지 나누어떨어지지 않음
				prime[ptr++] = n;			//소수라고 배열에 저장
				counter++;
			}
		}
		
		for(int i=0; i<ptr; i++)
			System.out.println(prime[i]);
		
		System.out.println("곱셈과 나눗셈을 수행한 횟수:" + counter);
	}
}

실행결과 ->

안쪽의 for문을 반복할때마다 counter를 2씩 증가시키는 것은 다음 두 연산의 수행 횟수를 계산하기 위해서이다.
- 곱셈   ....prime[i] x prime[i]
- 나눗셈 .....n % prime[i]

prime[i] x prime[i] <= n이 성립하지 않으면 수행 횟수에 포함이 되지 않는다.

그래서 for문 종료 후 counter++로 횟수 포함.