9도 OJ 1040: Prime Number(질량)(귀속)

시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 5278
해결
제목 설명:
Output the k-th prime number.
입력:
k≤10000
출력:
The k-th prime number.
샘플 입력:
3
7

샘플 출력:
5
17

출처:
2008년 상해교통대학 컴퓨터 연구 생기시험 진제
생각:
질수를 구하려면 시간의 복잡도를 주의해야 한다. sqrt(n)를 검색하면 질수 여부를 판단할 수 있다.
또한 여러 번 해답을 구하면 미리 수조를 저장하여 여러 번 해답을 구하는 것을 피할 수 있다.
코드:
#include <stdio.h>
#include <math.h>
 
int isprime(int n)
{
    for (int i=2; i<=sqrt(n); i++)
    {
        if (n%i == 0)
            return 0;
    }
    return 1;
}
 
int kthprime(int k)
{
    int n = 1;
    while (k--)
    {
        n++;
        while (! isprime(n))
            n++;
    }
    return n;
}
 
int main(void)
{
    int k;
 
    while (scanf("%d", &k) != EOF)
    {
        printf("%d
", kthprime(k)); } return 0; } /************************************************************** Problem: 1040 User: liangrx06 Language: C Result: Accepted Time:70 ms Memory:928 kb ****************************************************************/

좋은 웹페이지 즐겨찾기