소수의 개수

문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.

입력 예제
20

출력 예제
5

답

public class problem15 {

	public static void main(String[] args) {
		int input = 20;
		int cnt = 0;
		
		for(int i=2; i<input; i++) {
			
			boolean isPrime = true;	
			
			//제곱근(j*j)까지만 돌리면 된다.
			for(int j=2; j*j<=i; j++) {
				
				if(i%j==0) {
					isPrime = false;
					break;
				}
			}
			
			if(isPrime)
				cnt++;				
		}
		
		System.out.println(cnt);		

	}

}