FORTIS FORTUNA ADIUVAT

소수(Prim Number)란?

소수(Prime Number)는 약수로 1과 자기 자신만을 약수로 가지는 정수입니다. 
예를 들어, 
8의 약수는 "1, 2, 4, 8" 입니다. 1과 8 이외에 2,4를 약수를 가지고 있어 8은 소수가 되지 않습니다.
11의 약수는 "1, 11"인데, 1과 11을 약수로 가지는데요. 즉, 1과 자기 자신만을 가지게 되므로 11은 소수 입니다.

소수(Prim Number) 구하기 풀이1

2~1000000의 범위에서 소수를 구해 봤습니다.(1은 소수가 아니므로 제외)
반복문(for문)을 두번 사용하여 1을 제외한 단순히 범위에 따라서 모든 수를 나누어 주었습니다.

8 => 2,3,4,5,6,7,8 / 2로 나누어 짐 소수 X (break; 실행)
9 => 2,3,4,5,6,7,8,9 / 3으로 나누어짐 소수 X (break; 실행)
10 => 2,3,4,5,6,7,8,9,10 / 2으로 나누어짐 소수 X (break; 실행)
11 => 2,3,4,5,6,7,8,9,10,11 / 어떤수로도 나누어 지지 않음 O(소수)

풀이 1은 위와 같이 2~1000000까지 모두 수행하여 소수를 구했습니다. 
실행 결과를 보면 127.133초 / 나누기 횟수는 37567404990번 했다는 것을 알 수 있습니다.
풀이 2에서 이제 성능을 개선 해보도록 하겠습니다.

소스코드

public class PrimNumber1 {
	public static void main(String[] args) {
		long count = 0L;				// 나눗셈 횟수
		
		double beforeTime = System.currentTimeMillis();
		
		for(int i = 2; i <= 1000000; i++) { 
			int j;
			for(j=2; j<=i; j++) {
				count++;
				if(i%j == 0)
					break;
			}
			if(i==j)
				System.out.println(i);
		}
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행 결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 127.133
나누기 횟수 : 37567404990

소수(Prim Number) 구하기 풀이2

풀이 2에서는  11.382초 / 나누기 횟수 3084786715번 했다는 것을 확인 했습니다.
풀이 1알고리즘 보다는 조금더 성능이 좋아 졌습니다.
풀이 2에서는 2는 소수임을 인지하고 배열에 2를 prime배열에 저장하고 
2를 제외한 나머지 짝수는 전부 2로 나누어 지기때문에 소수가 될 수 없음을 알고, 
홀 수만을 소수를 구해야 되는 범위로 잡고, 홀수 임에도 기존에 찾은 수소들과 다시 나누어 
나누어 지지 않으면 소수로 판별 하여 구하였습니다.
정리하면,

1. prime 배열에 소수 2를 저장
2. prime 배열에 저장되어 있는 기존에 구했던 소수를 이용해 정수를 나누어 준다.
  - i = 3 / prime => {2} : i / prime[0](3/2) 는 나누어 지지 않는다 => 소수O => prime 배열에 저장
  - i = 4 / prime => {2,3} : i / prime[0](4/2) 는 나누어 진다 => 소수X
  - i = 5 / prime => {2,3} : i / prime[0](5/2) 는 나누어 지지 않는다 => 소수O => prime 배열에 저장

위와 같은 방법으로 성능을 개선 하였습니다. 하지만, 알고리즘 성능은 풀이1보다 더 좋아졌지만
배열을 사용하기 때문에 메모리(자원)를 더 많이 사용 하는 것을 알 수 있습니다.
풀이 3에서는 에라토스테네스의 접근 방법을 사용하여 성능과 자원사용을 더 개선 해보겠습니다.

소스코드

public class PrimNumber2 {
	public static void main(String[] args) {
		long count = 0L;				// 나눗셈의 횟수
		int ptr = 0;					// 찾은 소수의 개수
		int[] prime = new int[500000];	// 소수를 저장
		
		prime[ptr++] = 2;			// 2는 소수이다
		
		double beforeTime = System.currentTimeMillis();
		
		// 홀수만 검사 -> 짝수는 2를 제외 전부 소수 이기때문(2로나눠짐)
		for(int i = 3; i<=1000000; i+=2) {
			int j;
			// 기존에 찾은 소수로 나누어 나눠지지 않으면 소수
			for(j=1; j < ptr; j++) {
				count++;
				if( (i%prime[j]) == 0)
					break;
			}
			if( ptr == j )
				prime[ptr++] = i;
		}
		
		for(int i = 0; i < ptr; i++)
			System.out.println(prime[i]);
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 11.382
나누기 횟수 : 3084786715

소수(Prim Number) 구하기 풀이3

위와 같이 제곱근(루트) 값을 알 수 있는데요.

아래와 같은 방법으로 "2~N의 제곱근"의 범위로 잡고 나누어 소수를 판별 할 수 있습니다.

i = 2, j=2, j <= 1.xxx  →  j <= 1.xxx (2 < 1.xxx) 거짓  →  소수O
i = 3, j=2, j <= 1.xxx  →  j <= 1.xxx (2 < 1.xxx) 거짓  →  소수O
i = 4, j=2, j <= 2  → j <= 2 (2 <= 2) 참 → 4%2==0 참 → 소수X
i = 5, j=2, j <= 2.xxx → j <= 2.xxx(2<=2.xxx) 참 → 5%2==0 거짓 → 소수O
i = 6, j=2, j <= 2.xxx → j <= 2.xxx(2<=2.xxx) 참 → 6%2==0 참 → 소수X

소스코드

public class PrimNumber3 {
	public static void main(String[] args) {
		int count = 0;
		
		double beforeTime = System.currentTimeMillis();
		
		for(int i = 2; i<=1000000; i++) {
			boolean isPrim = true;
			for(int j=2; j<=Math.sqrt(i); j++) {
				count++;
				if( (i%j)==0 ) {
					isPrim = false;
					break;
				}
			}
			
			if( isPrim )
				System.out.println(i);
			
		}
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 1.008
나누기 횟수 : 67740404