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

본 포스팅은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 Java편'을 스터디 한 내용입니다.

 

방법 1, 2, 3으로 진행되면서 나눗셈 횟수를 줄이는 방향으로 알고리즘을 개선함.

---

방법 1.

2부터 n을 1씩 증가시키며, 그 값이 소수인지 판단함.

이중 for문의 안쪽에서 n까지 i를 1씩 증가시키면서 나누어떨어지면 break;를 통해 반복문을 탈출함.

그동안 counter++되면서 나눗셈 횟수를 증가시킴.

 

짝수 및, 소수의 배수들 또한 반복적으로 테스트함으로 불필요한 나눗셈 횟수가 많아짐.

/**
 * @Date 2020. 1. 26.
 * @Time 오후 4:03:00
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class primeNumber1 {

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 26.
	 * @Method Name : main
	 * @return : void
	 */
	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.

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

소수를 저장하고, 저장된 소수로 나누어 떨어지는가를 판단함.

3이상의 소수는 2씩 증가시키며, 홀수만 판단함.

/**
 * @Date 2020. 1. 26.
 * @Time 오후 4:09:54
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class primeNumber2 {

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 26.
	 * @Method Name : main
	 * @return : void
	 */
	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=0; 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);
		

	}

}

 

방법 3.

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

100을 예로들면, 2x50, 4x25, 5x20, 10x10, 20x5, 25x4, 50x2로 10x10을 중심으로 대칭을 이룸.

이는 10까지만 나눗셈을 시도하고 그 과정에서 나누어떨어지지 않으면, 소수로 판단해도 좋다는 의미.

 

/**
 * @Date 2020. 1. 26.
 * @Time 오후 4:25:27
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class primeNumber3 {

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 26.
	 * @Method Name : main
	 * @return : void
	 */
	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) { //2,3은 소수이고 홀수만 판단
			
			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);

	}

}