java 소수 구하기 + 실행시간 단축

소수(Prime Number) 

: 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수

Contents

첫번째, n 보다 작은 정수를 나누어 보며 소수 구하는 법

두번째, 1번 방법 마법의 코드 한줄을 통해 실행 시간 단축하는 법

세번째, n 보다 작은 소수를 나누어 보며 소수 구하는 법

첫번째, n 보다 작은 정수를 나누어 보며 소수 구하는 법

public class prime {
    public static void getPrime(int num){
        boolean flag;    //소수 판별을 위한 true/false
        int cnt = 0;     //소수의 총 개수를 확인하기 위한 변수
        for(int i=2; i<=num; i++){    //i는 2~num 사이에 정수
            flag = true;
            for(int j=2; j<i; j++){   //j는 i보다 작은 정수
                if(i%j ==0){          //i를 j로 나누었을 때, 나누어 떨어지면 소수가 아님
                    flag = false;
                }
            }
            if(flag == true){
                cnt++;
                System.out.println(i); //소수를 따로 배열에 저장하지 않고, 찾을 때 마다 출력
            }        
        }
        System.out.println("소수 개수 : " + cnt);
    }
    
    public static void main(String[] args){
        long start = System.currentTimeMillis();
        getPrime(30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}

실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 2.214(s)

총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 2.214초

두번째, 1번 방법 마법의 코드 한줄을 통해 실행 시간 단축하는 법

첫번째 코드의 public static void getPrime(int num){ ~ } 함수 안에 for문을 유심히 보자.

for(int i=2; i<=num; i++){ 

   flag = true;

   for(int j=2; j<i; j++){ 

      if(i%j ==0){        

          flag = false;

      }

   }

   if(flag == true){

      cnt++;

      System.out.println(i); 

   }        

}

i=9일 경우,

for(int j=2; j<i; j++){ 

   if(i%j ==0){        

       flag = false;

   }

}

j=3일 때, 이미 flag 값은 false가 된다. 9는 3의 배수 중 하나이기 때문에 소수가 아니다.

하지만 첫번째 방법의 소수 판별문의 경우, 

이미 flag값이 false가 되어 소수가 아닌 숫자를 찾아내도, 지속적으로 i값 보다 작은 정수를 나누어 보며 비교한다.

필요없는 연산이 계속해서 일어나고 있는 것이다.

이런 필요없는 연산을 줄이기 위한 코드가 있다.

public class prime {
    public static void getPrime(int num){
        boolean flag;
        int cnt = 0;    
        for(int i=2; i<=num; i++){
            flag = true;
            for(int j=2; j<i; j++){    
                if(i%j ==0){        
                    flag = false;
                    break;	//마법의 코드
                }
            }
            if(flag == true){
                cnt++;
                System.out.println(i);
            }        
        }
        System.out.println("소수 개수 : " + cnt);
    }

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        getPrime(30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}

10번 줄의 break문을 추가하여, i가 한 번이라도 j값을 통해 나누어 떨어지면, 

i는 이미 소수의 조건을 박탈, break문을 통해 해당 for문에서 빠져나와 새로운 값의 비교 연산을 진행한다.

실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 0.254(s)

총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 0.245초

break; 코드 한 줄을 통해 실행시간이 10배 가까이 단축 된 것을 볼 수 있다.

세번째, n 보다 작은 소수를 나누어 보며 소수 구하는 법

위의 2가지 방법은 

입력 받은 수보다 작은 수들을 나누어보며 떨어지는지 아닌지 판별을 하고 있다.

잘 생각해보면, 우리는 더 좋은 방법을 찾을 수 있다.

4는 2의 배수다. 2는 소수다.

10은 2의 배수, 5의 배수다. 2와 5는 소수다.

21는 3의 배수, 7의 배수다. 3과 7은 소수다.

입력 받은 수 보다 작은 정수들을 다 나누어 볼 필요없이,

입력받은 수보다 작은 수의 소수들만 나누어보면 되는 것이다.

import java.util.ArrayList;
 
public class prime {
    public static void getPrime(ArrayList<Integer> prime , int num){
        int cnt = 0;
        prime.add(2);
        for(int i=2; i <= num; i++){
            for(int j=0; j<prime.size(); j++){
                if(i%prime.get(j)==0){
                    break;
                }
                if(j+1 == prime.size()){
                    prime.add(i);
                }
            }
        }
        for(int i = 0; i<prime.size(); i++){
            cnt++;
            System.out.println(prime.get(i));
        }
        System.out.println("소수 개수 : " + cnt);
    }
    public static void main(String[] args){
        long start = System.currentTimeMillis();
        ArrayList<Integer> prime = new ArrayList<Integer>(); 
        getPrime(prime, 30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}

실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 0.072(s)

총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 0.072초

첫번째 코드 보다는 30배 가까이,

두번째 코드 보다는 3배 가까이 실행 시간이 단축 된 것을 볼 수 있다.

3가지 방법 정수의 개수에 따른 실행 속도 비교

1000개 까지의 정수 중 소수를 판별하기 위한 실행속도는 방법별로 큰 차이는 보이지 않는다.

하지만 숫자가 커지면서 방법 별 실행속도의 차이는 눈에 띄게 차이가 나는 것을 볼 수 있다.

출처: http://hahahoho5915.tistory.com/14?category=653539 [넌 잘하고 있어]