문제
다음은 한결이가 거울과 한 얘기중 일부이다.
- 한결 : 난 아무리 생각해도 기억력이 좋은 것 같아!
- 거울 : 양심없니?
- 한결 : 이걸 못 믿니? 너무 어이없네 ㅋㅋ
- 거울 : ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ
- 한결 : 하.. 이걸 못 믿네; 내 머릿속에 지금 모든 소수가 차례대로 들어가 있거든? 니가 원하는 번째의 소수를 대답해줄게
- 거울 : 그럼 k번째 소수가 뭔데??
- 한결 : k번째 소수는....
솔직히 한결이는 기억력이 쓰레기다. 그래서 소수를 외우고 있지 못하다. 하지만 이렇게 허세를 부리고 나니 거울한테 참교육을 시전해주고 싶었다. 한결이를 도와 k번째 소수를 알려주자.
소수의 정의는 다음과 같다.
2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다.
입력
자연수 K가 주어진다.(1 ≤ K ≤ 500,000)
출력
K번째 소수를 출력하자.
서브태스크 1 (5점)
- K ≤ 5000
서브태스크 2 (20점)
- K ≤ 40000
서브태스크 3 (75점)
문제에서 주어진 제약 조건 외 조건 없음
예제 입력 1
1 |
예제 출력 1
2 |
예제 입력 2
3 |
예제 출력 2
5 |
채점 및 기타 정보
- 예제는 채점하지 않는다.
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
int main(void)
{
int K, count=1, number;
bool sieve[7368788]={false, };
for(int i=3;i<7368788;i+=2)
sieve[i]=true;
for(int i=3;i<7368788;i+=2)
if(sieve[i])
for(int j=2*i;j<7368788;j+=i)
sieve[j]=false;
scanf("%d", &K);
if(K==1)
printf("2\n");
else
{
for(number=3;count<K;number+=2)
count+=sieve[number];
printf("%d\n", number-2);
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 17103번: 골드바흐 파티션 (0) | 2020.11.28 |
---|---|
<백준 알고리즘> 12756번: 고급 여관 (0) | 2020.11.28 |
<백준 알고리즘> 13866번: 팀 나누기 (0) | 2020.11.28 |
<백준 알고리즘> 14726번: 신용카드 판별 (0) | 2020.11.27 |
<백준 알고리즘> 2903번: 중앙 이동 알고리즘 (0) | 2020.11.26 |