[Java] 2-5 소수(에라토스테네스 체)

문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

입력
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
출력
첫 줄에 소수의 개수를 출력합니다.
예시 입력

20

예시 출력

8

출처
인프런 - 자바-알고리즘-문제풀이-코테대비

내 풀이

에라토스테네스 체

private static int countPrimeNumber1(int num) {
    long start = System.nanoTime();
    boolean[] isNotPrime = new boolean[num + 1];

    int count = 0;

    for (int i = 2; i <= num; i++) {
        if(!isNotPrime[i]) {
            // 소수의 배수는 false
            for (int k = 2; k * i <= num; k++) {
                isNotPrime[k * i] = true;
            }
            count++;
        }
    }
    long end = System.nanoTime();
    System.out.printf("실행시간1: %10d ns\n", end-start);
    return count;
}

찾은 소수의 배수는 제외한다
isPrime으로 하고 모든값을 true로 초기화하면 초기화 시간이 많이 소모돼서 isNotPrime을 사용함

---

전부나눠보기

private static int countPrimeNumber2(int num) {
    long start = System.nanoTime();
    int count = 0;

    for (int i = 2; i <= num; i++) {
        count++; // 일단 1 올린다
        for (int j = 2; j < i; j++) { // 2 ~ (i-1)로 나눠본다
            if (i % j == 0) {
                count--; // 약수가 발견되면 1감소
                break;
            }
        }
    }
    long end = System.nanoTime();
    System.out.printf("실행시간2: %10d ns\n", end-start);
    return count;
}

모든 경우의 수

---

실행시간

100
실행시간1:       4700 ns
실행시간2:      14000 ns
10000
실행시간1:     483100 ns
실행시간2:    8518100 ns
100000
실행시간1:    1691300 ns
실행시간2:  583762100 ns

기억할 점

자바 코드 실행시간 측정

long start = System.nanoTime();
long end = System.nanoTime();
System.out.printf("실행시간: %10d ns\n", end-start);