[ 자바 알고리즘/자료구조] - 자바 소수 나열 ( 성능 개선버전 추가 )

이번에는 정수 이하의 소수를 나열하는 알고리즘을 살펴보겠다.

 

소수란?

- 자신과 1외에 정수로 나누어지지 않는 정수를 말한다.

 

public class 소수나열 {
	public static void main(String[] args){
		int cnt = 0;
		for(int i=2; i<=1000; i++){
			int j;
			for(j=2; j<i; j++){
				cnt++;
				if(i % j == 0){
					break;
				}
			}
			if(i == j){
				System.out.println(i);
			}
		}
		System.out.println("나눈 수 : " + cnt);
	}
}

2부터 1000까지의 숫자중 소수를 나열하는 코드이다.

- cnt라는 나눈횟수를 저장할 변수를 하나 선언한다.

- 첫번째 for문에서 대상이 되는 숫자를 반복한다.

- int j는 2번째 for문안에 선언해도 되지만 지역변수 특성상 2번째 for문을 벗어나면 소수들을 나열할 수 없어서 첫번째 for문안에 선언했다.

- 우선 i에 값에서 j값을 나눈 나머지가 0이된다면 소수가 아니기때문에 break를 통해 벗어난다.

- 그렇지 않으면 계속해서 나눗셈 연산을 수행하며 cnt값을 증가시킨다.

- if문을통해 i와 j의 값이 같아지면 출력을 시켜주었다.

 

 

****** 근데 위에 코드에서는 불필요한 연산이 많이있다. *******

- 대상이 되는 숫자보다 작은 소수로 나누어 떨어지지 않으면 계산 시작을 줄일 수 있다.

 

public class 소수나열개선1 {
	public static void main(String[] args){
		int cnt = 0;
		int idx = 0;
		List<Integer> list = new ArrayList<>();
		list.add(2);
		idx++;
		for(int i=3; i<=1000; i+=2){
			int j;
			for(j=1; j<idx; j++){
				cnt++;
				if(i % list.get(j) == 0){
					break;
				}
			}
			if(idx == j){
				list.add(i);
				cnt++;
			}
		}
		for(int i=0; i<list.size(); i++){
			System.out.println(list.get(i));
		}
		System.out.println("나눈 수 : " + cnt);
	}
}

 다음은 위 코드보다 더 간결하고 성능을 고려한 코드이다.

- 우선 배열을 사용해도 되지만 int 타입 배열을 빈공간은 0으로 채워지기 때문에 보기가 싫다. 그래서 컬렉션중 하나인 list를 사용했다. -> list의 열할은 소수들을 담는다. 여기서는 홀수만 계산할건데 2로 나누어 지지 않으면 나머지 소수인 애들로만 대상이 되는 숫자를 나눴을때 0이 안되면 대상이 되는 수도 소수이기 때문이다.

- 우선 list에 2를 담아준다. -> 2는 어짜피 소수이기 때문

- 그리고 for문을 보면 3부터 2씩 증가 즉, 홀수만 계산을한다. 왜? -> 짝수는 어짜피 2로 나누어 지기 때문

- 다음 for문에서 cnt값 ( 연산값 )을 증가시키고, i (대상이되는 수) 가 list에 담긴 숫자들로 나누었을때 0이 남으면 멈춤

- idx값과 j값이 같으면 저장된 소수들로 나누어 지지 않았기 때문에 해당 값도 소수이므로 list에 저장한다.

 

** 참고로 2번째 for문에서 의문점이 생길 수 있다. j가 1로 시작하고. idx값이 1보다 작을때 까지면 for문이 안돌거 아닌가? -> 맞다. 즉 3도 소수인데 다음 if문에서 3이 list에 들어가게 되고 idx는 2가된다. 

 

-- 자 첫번째 코드에서는 연산 수가 78022회고, 두번째 코드는 14622회다

-- 눈에 띄게 좋아졌지만 뭔가 찝찝하다.. 14622도 너무 많다. 더 줄여보자.

 

 

 

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

- sosu[i]가 n제곱 이하인가?

 

public class 소수나열개선2 {
	public static void main(String[] args){
		int cnt = 0;
		int idx = 0;
		int sosu[] = new int[500];
		
		sosu[idx++] = 2;
		sosu[idx++] = 3;
		
		for(int i = 5; i <= 1000; i += 2){
			boolean flag = false;
			for(int j = 1; sosu[j] * sosu[j] <= i; j++){
				cnt+=2;
				if(i % sosu[j] == 0){
					flag = true;
					break;
				}
			}
			if(!flag){
				sosu[idx++] = i;
				cnt++;
			}
		}
		for(int i=0; i<sosu.length; i++){
			if(sosu[i] != 0)
				System.out.println(sosu[i]);
		}
		System.out.println("총 연산 : " + cnt);
	}
}

- 우선 sosu배열에 0,1번째에 각각 2,3을 넣었다.

- 4는 짝수이므로 2로 나누어진다. 그러므로 첫번째 for문은 5부터 홀수만 돌려준다.

- boolean 타입의 flag의 초기값을 false로 선언한다.

- 두번째 for문에서 j는 1부터 시작하되, i가 sosu[j] 제곱보다 크면 나눠지지 않기때문에 불필요한 연산을 줄인다.

- 만약 제곱이 더 작다면 i 나누기 sosu[j]의 나머지가 0인지 확인하고 flag를 true로 변환 후 break로 빠져나간다.

 ( cnt를 2증가 시킨 이유는 for문에서 곱셈연산과 if문에서 나눗셈 연산이 2번 들어가기 때문이다 )

- 만약 flag가 그대로 false라면 소수이므로 배열에 추가해준다.

-> 이 코드의 총 연산은 3774회이다. 앞에 2코드에 비하면 엄청나게 줄어든 연산횟수이다.