글 읽기 - 6542 질문

onjo0127 8년 전 0

이 문제 n번째 소수를 찾는 문제 아닌가요?

에라토스테네스의 체를 응용한 알고리즘입니다.

시간초과도 아니고 아예 틀렸다고 나오네요.

틀린 점 지적해주세요!

#include <stdio.h>
int arr[99999];
int prime[99999];
int main()
{
    int n,i,j,cnt=0;
    for(i=2;i<=99999;i++)arr[i]=i;
    for(i=2;i<=55555;i++) {
        if(arr[i]==0)continue;
        for(j=i+i;j<=99999;j+=i)arr[j]=0;
    }
    for(i=2;i<=99999;i++){
        if(arr[i]!=0)prime[cnt++]=arr[i];
    }
    while(1) {
        scanf("%d",&n);
        if(n==0)break;
        printf("%d\n",prime[n-1]);
    }
    return 0;
}

ntopia 8년 전 0

n번째 소수 찾는 문제가 아닌 것 같네요....

onjo0127 8년 전 0

그럼 무슨 문제이죠?

해석을 못하겠어요;;

ntopia 8년 전 2

자연수가 2부터 죽 늘어서있는데,

매 스텝마다 맨 앞에 있는 자연수 k가 lucky number 가 되고

그 수 뒤로 k번째 마다 놓여있는 자연수를 지웁니다.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31

5 7 11 13 17 19 23 25 29 31

7 11 13 17 23 25 29 31

뭐 이런식으로요... (지워지는 수에 밑줄을 쳐보았습니다.)

위의 예에서 19는 소수이지만 3번째 스텝에서 지워집니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6542 질문

onjo0127 8년 전 0

ntopia 8년 전 0

onjo0127 8년 전 0

ntopia 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말