23/02/03 [⭐Inf_0203 소수(에라토스테네스 체)]

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

 

예시 입력 1 

20

 

예시 출력 1

8

 

내코드 : 풀긴 했지만 시간초과

반복문 안의 조건문 안의 반복문 안의 조건문...

import java.util.Scanner;

public class Main {
    //        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  총21개
    // int[] [0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0]
    // int[] [1 1 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0]

    public int solution(int n){
        int answer = 0;
        int[] ia = new int[n+1];
        ia[0] = 1; ia[1] = 1; // 0과 1은 소수가 아님을 표시

        for(int i=0; i<=n; i++){
            if(ia[i] == 0){ // 소수라면
                answer++; // 카운트하고
                ia[i] = 1; // 소수로 판단했음을 표시
                for(int j=i+1; j<=n; j++){ // 자신의 배수를 찾기 위한 반복문
                    if(j%i == 0){ // 만약 자신의 배수면
                        ia[j] = 1; // 소수가 아님을 표시
                    }
                }
            }
        }

        return answer;
    }

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

 

강의코드

기억할 것

배열의 모든 요소를 검사하면서 자신의 배수인지 판단하는 것은 비효율적임.

반복문을 돌릴 때 자신의 배수만 검사하고 소수가 아님을 표시하도록 설정. for(int j=i; j<=n; j=j+i){ ia[j] = 1; }

import java.util.Scanner;

public class Main {
    //        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  총21개
    // int[] [0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0]
    // int[] [1 1 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0]

    public int solution(int n){
        int answer = 0;
        int[] ia = new int[n+1];

        for(int i=2; i<=n; i++){ // 애초에 2부터 시작
            if(ia[i] == 0){ // 소수라면
                answer++; // 카운트
                for(int j=i; j<=n; j=j+i){ // 배열 모든 요소들을 검사하는 것이 아니라 자신의 배수만 검사
                    ia[j]=1; // 소수가 아님을 판단
                }
            }
        }

        return answer;
    }

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