shumin   2달 전

단순한 소수 찾기 문제인데

시간초과로 인해서 pass를 못했습니다.

에라토스테네스의 체 알고리즘을 사용해야 하는건가요?

아니면 제가 다른 문제가 있는걸까요?


혹시 아시는분 답변 부탁드리겠습니다.

sksdong1   2달 전

에라토스테네스의 체 알고리즘 사용하면 됩니다.

범위가 더 커졌을 경우 num~ 2*num사이의 수를 O(n) 에서 O(1)으로 줄이는 알고리즘도 고려해볼 수 있지만 여기까지 안해도 AC나오네요.

shumin   2달 전

아래와 같이 에라토스테네스 체 알고리즘을 적용했는데

아직 시간초과가 나오네요..

num ~ 2*num 의 소수의 수를 찾는 방법이 떠오르지 않아

2*num의 소수의 수 - num 의 소수의 수로 했는데 아직 시간초과가 발생합니다.

혹시 다른 조언 부탁드려도 가능할까요?

sksdong1   2달 전

매번 구할 필요 없이 소수는 처음에 구해 놓으면 됩니다 

어차피 소수의 수는 변하지 않죠..

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