일단 에라토스테네스의 체는 O(nloglogn)인데, 이 코드는 적어도 O(nsqrt(n))입니다.
에라토스테네스의 체는 소수에 대해서만 배수를 제거하는 식으로 더 줄일 수 있습니다.
그리고 오일러의 체도 있긴 합니다. 굳이 안 써도 될 것 같지만...
추가로 7번째 줄에 value in list가 빠르게 계산될지는 모르겠습니다. 또한 소수에 대해서만 배수를 제거하는 식으로 하려면 boolean list(array)로 표현하는 것이 나을 수 있습니다.
tlawotjd123 3년 전
b보다 작거나 같은 자연수 제곱근들을 for문돌려 while문을통해 그 제곱근들의 배수를 빼주는 과정
즉 에라토스테네스의 체를 활용하여 코드를 짰습니다.
나름 줄인다고 고민많이하고했는데 어느부분에서 줄여야할지 이제 감이안오네요
고수님들 살려주십쇼