문제요약:
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
구현코드:
class Solution {
public int solution(int n) {
int answer = 0;
for(int i=2;i<=n;i++){
int count=0;
for(int j=2;j<i;j++){
if(i%j==0){
count++;
break;
}
}
if(count==0) answer++;
}
return answer;
}
}
코드해석:
문제만 본다면 참 쉬운 문제이다 . 하지만 이 코드는 효율성에서 실패한다. 이유는 다음과 같다.
모든 수를 검사하기 때문에 양이 많아진다면 효율성에서 좋지않다고 한다. 그래서 다른방법으로 풀어야하는데
에라토스테네스의 체 방법으로 사용해보았다.
에라토스테네스의 체 방법은 배수는 소수가 아니다를 이용한 방식이다. 그래서 n보다 작은 수를 반복하여 i의 배수인 수를 비교하지
않는방법이다.
class Solution {
public int solution(int n) {
int answer = 0;
int[] list = new int[n+1];
list[0]=0;
list[1]=0;
for(int i=2;i<=n;i++) list[i]=i;
for(int i=2;i<n;i++){
if(list[i]==0) continue;
for(int j=2*i; j<=n; j+=i) list[j] = 0;
}
for(int i=0; i<list.length; i++) {
if(list[i] != 0) answer++;
}
return answer;
}
}