소수(에라토스테네스 체)

설명

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

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

 

입력

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

 

출력

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

예시 입력 1 

20

 

예시 출력 1

8

 

소스 코드 1 (시간 초과)

package section2;

import java.util.Scanner;
//시간초과걸림
public class Ex05 {
    public static int solution(int N) {
        int ans = 0;
        for (int i = 2; i <= N; i++) { //1은 소수가 아님
            for (int j = 2; j <= i; j++) { //1과 자신 이외에 나눠지는 수가 없어야 소수
                if (i % j == 0) {//if 4 ) 4,2 4,3 4,4 / 4,4만 맞아야함 근데 4,2도 나눠짐
                    if (i / j != 1) {
                        break;
                    }
                    ans++;
                }
            }
        }
        return ans;
    }

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

 

소스 코드 2

import java.util.Scanner;

public class Main {
    public static int solution(int N) {
        int ans = 0;
        int[] arr = new int[N + 1];

        for (int i = 2; i <= N; i++) {//2부터 N까지 반복
            if (arr[i] == 0) { //만약 0 이라면 카운트 해준다.
                ans++;
                
                //배수를 모두 1로 만든다. 여기서 j+=i가 아닌 j++로 검증한다면 시간초과 걸림.
                for (int j = i; j <= N; j+=i) {
                    arr[j] = 1;
                }
            }
        }
        return ans;
    }

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