[Java] 소수 개수 구하기 | 인프런 | 에라토스테네스 체

문제

 

풀이 1 - 시간 초과 (직관적인 방법)

소수란 1과 자기 자신으로만 나누어 떨어지는 수입니다.(=다른 수 나머지 연산을 했을 경우에 나머지가 0이 나오면 안 되는 수)

숫자 x를 소수인지 확인하려면, 2부터 x/2까지 수로 나머지 연산을 시도해서 나누어 떨어지는 지 검사하면 됩니다. 나누어 떨어지면 소수가 아닙니다.

 

/*
* N을 입력하면 1부터 N까지 수 중 소수의 갯수를 출력하는 문제
*
*
* */

import java.util.Scanner;

public class Main {
    public static int solution(int n) {
        int count = 0;
        for (int i=2; i<=n; i++) {
            if (isPrime(i)) count++;
        }
        return count;
    }

    public static boolean isPrime(int n) {
        for (int i=2; i<=n/2; i++) {
            if (n%i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solution(n));
    }
}

 

하지만 이 풀이는 시간초과가 나왔습니다.

단순 이중 반복문을 사용하면 입력이 20만이니, 약 400억 연산을 해야 되고 1억 번 연산이 보통 1초가 걸리니 최악의 경우 400초가 걸릴 수 있습니다. 

따라서 ,

소수를 빠르게 구하고 싶은면 에라토스테네스 채 방법을 이용하면 됩니다.

 

풀이 2 - 에라토스테네스 채 방법 

소수를 구하는 방법 중 가장 빠른 방법입니다. 

알고리즘은 다음과 같습니다.

- 2부터 소수를 구하고자 하는 구간(n)의 수를 나열합니다.

- 2부터 n까지 검사합니다.

- 2는 소수이므로 카운팅 하고, 2를 제외한 2의 배수를 모두 제거합니다.(소수는 1과 자기 자신을 제외하고 나누어 떨어지면 안 되는데, 2를 제외한 2의 배수는 모두 2를 약수로 가지고 있기 때문에 나누어 떨어집니다.)

- 3은 소수이므로 카운팅하고, 3을 제외한 3의 배수를 모두 제거합니다.

- 4는 제거되었으니깐 건너뜁니다.

- 반복

 

/*
* N을 입력하면 1부터 N까지 수 중 소수의 갯수를 출력하는 문제
*
*
* */

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int solution(int n) {
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);
        int count = 0;
        isPrime[0] = false;
        isPrime[1] = false;


        for (int i=2; i<=n; i++) {
            if (isPrime[i]) {
                count++;
                for (int j = i*2; j<=n; j = j+i) {
                    isPrime[j] = false;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solution(n));
    }
}

 

새로 배운 것

Java.util.Arrays - fill(배열, 값)

배열의 원소를 해당 값으로 초기화합니다.