알고리즘 문제
[C/C++ 백준 2960번] 에라토스테네스의 체 (Silver 4)
새파란 공대생
2020. 7. 22. 12:39
https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾
www.acmicpc.net
수학 알고리즘에서 많이 썼던 알고리즘인데, 지금 본게 살짝 아쉬운 문제.
코드는 다음과 같다.
#include <cstdio>
int main(void){
int N, K, number[1001]={}, cnt=0, ans;
bool STOP = false;
scanf("%d %d",&N,&K);
for(int i=2; i<=N; i++){
if(number[i]==0){
for(int j=i; j<=N; j += i){
if(number[j]==0){
number[j]=-1;
cnt++;
if(cnt==K){
STOP = true;
ans = j;
break;
}
}
}
}
if(STOP)
break;
}
printf("%d", ans);
}