[Programmers 프로그래머스] 12921 소수 찾기

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

입력값의 소수를 찾는 문제이다.

큰 숫자의 소수를 찾을때에는 root를 이용해야 시간초과가 나지 않는다.

그래서 root값을 이용을 해서 for문을 돌면서 소수인 값을 false로 만들어 주고, false의 수를 세어주어 값을 출력한다.

import java.util.Arrays;

class Solution {
    public int solution(int n) {
		int answer=0;
		boolean []sosu=new boolean[n+1];
		Arrays.fill(sosu, true);
		int root=(int)Math.sqrt(n);
		for (int i = 2; i <= root; i++) {
			if(sosu[i]==true) {
				for (int j = i; i*j <= n; j++) {
					sosu[i*j]=false;
				}
			}
			
		}
		for (int i = 2; i <=n; i++) {
			if(sosu[i]==true) {
				answer++;
			}
		}
        return answer;
    }
}