JAVA/알고리즘

N까지 소수 개수 구하기 JAVA

lovineff 2021. 5. 13. 16:31

에라토스테네스의 체 사용하여 해결

/*
자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.
▣ 입력설명
    첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
▣ 출력설명
    첫 줄에 소수의 개수를 출력합니다.
▣ 입력예제 1
    20
▣ 출력예제 1
    8
 */
public class Question5 {
    /*
    * 에라토스테네스 체 사용
    * */
    public static int solution(int N){
        int result = 0;
        int[] arr = new int[N+1];       // 배열의 모든 값은 0으로 초기화됨

        for (int i = 2; i <= N; i++) {  // 2부터 N까지
            if(arr[i] == 0){            // 체크되지 않은 값인 경우 소수
                result++;

                for (int j = i; j <= N; j=j+i) {    // 현재 i값의 배수들은 모두 체크처리 (소수가 아님)
                    arr[j] = 1;         // 배수는 소수가 아니므로 체크
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int solution = solution(20);
        System.out.println(solution);
    }
}

'JAVA > 알고리즘' 카테고리의 다른 글

등수 출력  (0) 2021.05.24
뒤집은 소수 구하기 JAVA  (0) 2021.05.13
피보나치수열 JAVA  (0) 2021.05.13
백준 10757 풀이  (0) 2021.05.06
백준 2839 풀이  (0) 2021.05.06