문제 이해
[ 입력형태 / 조건 ]
n
범위 | 10 | 2이상 1000000이하의 자연수
[ 문제 ]
=>1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 return
[ 풀이 ]
에라토스테네스의 체를 이용해 소수를 미리 구하고, 소수인지 판별하여 cnt 1 증가
코드
> [성공] 1차 시도 : 에라토스테네스의 체 이용
- 생각한 풀이 그대로 구현
class Solution {
public int solution(int n) {
boolean[] isNotPrime = new boolean[n+1];
for(int i=2; i<=(int)Math.sqrt(n); i++){
if(!isNotPrime[i]){
for(int j=i*i; j<=n; j+=i){
isNotPrime[j] = true;
}
}
}
int ans = 0;
for(int i=2; i<=n; i++){
ans += isNotPrime[i]?0:1;
}
return ans;
}
}
=> 생각보단 효율성 테스트에서 안타까운 결과를 보였음
> [성공] 2차 시도 : 에라토스테네스의 체 이용
- 소수를 다 구한 뒤에 개수를 구하는 것보단, 소수가 아니면 1 감소하는 형태로 구현하고자 했음
class Solution {
public int solution(int n) {
boolean[] isNotPrime = new boolean[n+1];
int ans = n-1;
for(int i=2; i<=(int)Math.sqrt(n); i++){
if(!isNotPrime[i]){
for(int j=i*i; j<=n; j+=i){
ans -= isNotPrime[j] ? 0 : 1;
isNotPrime[j] = true;
}
}
}
return ans;
}
}
=> 미미하지만, 전보다 빠르게 실행 가능했음
Tip : 에라토스테네스의 체를 구현할 때, 루트 범위까지만 봐도 소수를 전부 구분할 수 있다.
