[프로그래머스/Lv.1] 소수 찾기

1. Input, Output, Example

- 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환

- 소수는 약수의 개수가 2개인 자연수를 뜻한다.

 

2. Constraint

1) n은 2이상 1,000,000이하의 자연수

 

3. Code

import java.util.*;
class Solution {
    public int solution(int n) {
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, true);
        for(int i=2 ; i<=n ; i++)
            if(prime[i])
                for(int j=i*2 ; j<=n ; j+=i)
                    prime[j] = false;
        int count = 0;
        for(int i=2 ; i<=n ; i++)
            if(prime[i]) count++;
        return count;
    }
}

- +1