[자바] 소수 찾기

일반적인 알고리즘

import java.lang.reflect.Array;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        int n = 10;
        int answer = 0;
 
        for (int i = 2; i <= n; i++) {
            boolean flag = true;
            for (int j = 2; j < i; j++) {
 
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                answer++;
            }
        }
 
 
        System.out.println(answer);
 
    }
 
 
}
 

이 방식은 다 찾아봐야 하기 때문에 시간이 걸린다.

좀더 진보적인 방법은 

import java.lang.reflect.Array;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        long start = System.currentTimeMillis(); //시작하는 시점 계산
 
        int n = 100000;
        int answer = 0;
 
        for (int i = 2; i <= n; i++) {
            boolean flag = true;
            for (int j = 2; j*j <= i; j++) {
                if (i % 2 == 0) {
                    flag = false;
                    break;
                }else{
 
                    if (i % j == 0) {
                        flag = false;
                        break;
                    }
                }
 
            }
 
            if (flag) {
 
                answer++;
            }
        }
        System.out.println(answer);
        long end = System.currentTimeMillis(); //프로그램이 끝나는 시점 계산
        System.out.println("실행 시간 : " + (end - start) / 1000.0 + "초"); //실행 시간 계산 및 출력
 
    }
 
 
}
 

기존의 방식이 10000을 넣었을때 1초 정도 걸리면, 진보된 방식은 0.016초가 걸린다.

아마 소수를 구하는 방식의 경우 소수결과보단 출력 시간이 짧은 것을 원하는 형태일 것이다. 아마도...