002. Java의 기본 자료구조(소수나열)

소수 나열

 

먼저 소수가 되는 조건을 찾으면 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는 수 입니다.

 

코드로 표현하면 아래와 같이 표현할 수 있습니다.

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);
		}
	}
}

 

여기서 외부 for문에서는 1000이하의 소수를 구하는 프로그램이고, 소수중 제일 낮은 값은 2이므로 범위를 2~1000으로 정하였습니다.

 

그래고 내부 for문에서 i값을 추가시켜 n%i==0일경우 n값이 i값으로 나누어 떨어지는 정수가 존재하므로 소수가 아닙니다. 계속 진행하다보면 n==i값이 되는 수가 나오는데 이것이 1이나 자기 자신으로 나누어 떨어지는 소수입니다.

 

하지만 여기서 1000이하의 소숫값을 구할때 나눗셈은 총 78,022번 사용했습니다. 이러면 계산횟수가 너무 많아서 무거운 프로그램이라고 할 수 있습니다.

 

따라서 프로그램을 개선하겠습니다. 

 

개선방안-1

 

숫자마다 1부터 n까지 나누는 형식이 아닌 소수값을 배열에다가 저장해서 배열에 저장한 소수로 나누어 떨어지면 그 수는 소수가 아닙니다.

코드로 표현하면 아래와 같습니다.

 

public class PrimeNumber2 {
	public static void main(String[] args) {
		int counter = 0;
		int ptr = 0;
		int[] prime = new int[500];
		
		prime[ptr++] = 2; //prime[0]에 2를 대입한후 ptr를 증가시켰습니다. 
		
		for(int n=3;n<=1000;n+=2) {	// 대상은 홀수만 왜냐하면 짝수는 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++)
			System.out.println(prime[i]);
		System.out.println("나눗셈을 수행한 횟수 : "+counter);	// 14622회
	}
}

 

개선방안-2

 

n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않고 prime[i]의 제곱이 n이하인지 확인 합니다.

 

개선 한 코드

 

public class PrimeNumber3 {
	public static void main(String[] args) {
		int counter = 0;
		int ptr = 0;
		int[] prime = new int[500];
		
		prime[ptr++] = 2;
		prime[ptr++] = 3;
		
		for(int n = 5; n<=1000;n+=2) {
			boolean flag = false;
			for(int i =0; 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);
	}
}

 

여기서 개선방법 2번은 에라토스테네스의 체를 참고하시면 됩니다.

쉽게 설명하자면 1부터 50까지의 숫자중에서 소수를 구하려면 

 

50<8^2 이므로 8이하의 소수(2,3,5,7)의 배수만 제거해도 소수가 나옵니다.

1(x)	2(o)	3(o)	4(x)	5(o)	6(x)	7(o)	8(x)	9(x)	10(x)
11(o)	12(x)	13(o)	14(x)	15(x)	16(x)	17(o)	18(x)	19(o)	20(x)
21(x)	22(x)	23(o)	24(x)	25(x)	26(x)	27(x)	28(x)	29(o)	30(x)
31(o)	32(x)	33(x)	34(x)	35(x)	36(x)	37(o)	38(x)	39(x)	40(x)
41(o)	42(x)	43(o)	44(x)	45(x)	46(x)	47(o)	48(x)	49(x)	50(x)

2의 배수 :   

3의 배수 :   

5의 배수 :   

7의 배수 :   

그러면 여기서 소수인 숫자는 (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47)입니다.

 

참고 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전