onjo0127   1년 전

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

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

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

틀린 점 지적해주세요!

ntopia   1년 전

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

onjo0127   1년 전

그럼 무슨 문제이죠?

해석을 못하겠어요;;

ntopia   1년 전

자연수가 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번째 스텝에서 지워집니다.

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