[문제 설명]
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)
[에라토스테네스]
주어진 자연수 N이 소수이기 위한 필요 충분조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않음, 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 sqrt{N} 이하이기 때문
→ for문을 Math.sqrt(n)만큼 돌림
[에라토스테네스의 체]
모든 자연수는 소수들의 곱으로 표현이 됨. 제일 작은 소수 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복
class Solution {
public int solution(int n) {
int answer = 0;
int[] number = new int[n+1];
//2부터 n까지의 수를 배열에 넣는다.
for(int i=2; i<=n; i++) {
number[i] = i;
}
//2부터 시작해서 그의 배수들을 0으로 만든다.
//후에 0이면 넘어가고 아니면 그의 배수들을 다시 0으로 만든다.
for(int i=2; i<=n; i++) {
if(number[i]==0) continue;
for(int j= 2*i; j<=n; j += i) {
number[j] = 0;
}
}
//배열에서 0이 아닌 것들의 개수를 세준다.
for(int i=0; i<number.length; i++) {
if(number[i]!=0) {
answer++;
}
}
return answer;
}
}
JavaScript
복사
