Contents
문제
문제를 보시려면 링크를 클릭해주세요.
풀이
소수 구하기 최적의 알고리즘인 에라토스테네스의 체를 이용하면 간단하게 풀 수 있습니다.
주어진 숫자 크기의 배열을 만들어 모든 배수들을 체크해줍니다. (2의 배수, 3의 배수 …)
체크된 수는 그 배수들도 이미 체크가 되어있기에 넘어가줍니다.
최종적으로 체크 안된 수들이
소수임을 알 수 있습니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
vector<bool> chk(n+1, 0);
for(int i=2; i<=n; i++){
if(chk[i])
continue;
for(int j=i+i; j<=n; j+=i){
chk[j]=1;
}
}
for(int i=2; i<=n; i++){
if(!chk[i]){
answer++;
}
}
return answer;
}