[PS] 인프런 강의 - Array 5. 소수(에라토스테네스 체)

 

문제

자연수 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

풀이

자연수의 개수가 20만까지 갈 수 있고, 제한시간은 1초이기 때문에 이중 for문으로 풀면 안될거라 하심...

어떻게 풀어야할 지 감이 안와서 그냥 강의 봤다 ㅠ

 

코드

import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int[] ch = new int[n+1];
		int answer = 0;
		//1부터 n까지 소수 개수
		for(int i=2; i<=n; i++) {
			if(ch[i] == 0) {
				answer++; //소수
				for(int j=i; j<=n; j=j+i) ch[j] = 1; //소수의 배수를 모두 체크
			}
		}
		
		System.out.print(answer);
	}
}