문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
예제 입력 1
10 7 |
예제 출력 1
9 |
힌트
2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int main(void)
{
int N, K, count=0;
bool *sieve=NULL, reached=false;
scanf("%d %d", &N, &K);
sieve=(bool *)calloc(N+1,sizeof(bool));
for(int i=2;;i++)
{
if(!sieve[i])
for(int j=1;i*j<=N;j++)
{
if(!sieve[i*j])
{
sieve[i*j]=true;
count++;
}
if(count==K)
{
reached=true;
printf("%d\n", i*j);
free(sieve);
break;
}
}
if(reached)
break;
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 2460번: 지능형 기차 2 (0) | 2020.07.19 |
---|---|
<백준 알고리즘> 2455번: 지능형 기차 (0) | 2020.07.19 |
<백준 알고리즘> 11050번: 이항 계수 1 (0) | 2020.07.18 |
<백준 알고리즘> 10808번: 알파벳 개수 (0) | 2020.07.18 |
<백준 알고리즘> 10886번: 0 = not cute / 1 = cute (0) | 2020.07.18 |