Помогите добавить гипотезу простого числа К. Ф. Гаусса в мое сито Эратосфена

Question

Привет всем! Итак, я почти закончил с проблемой, над которой я начал работать для школы, которая имеет дело с Ситом Эратосфена. Мне удалось заставить программу распечатать все простые числа от 2 до квадратного корня из 1000. Однако мой учитель просит меня использовать гипотезу простых чисел (?) К.Ф. Гаусс. Вот что он говорит: C. Ф. Гаусс выдвинул гипотезу, что (N) определяется число простых чисел, меньших или равных N так как (N) = N / loge (N), когда N приближается к бесконечности. Это было названо простым числом гипотеза. В цикле for выведите простые числа, счетчик, указывающий его порядковый номер число (1, 2, 3 и т. д.) и значение (N).

Я пытался сделать еще один цикл for и печатать простые числа, но он просто не работает для меня! тьфу Любая помощь будет принята с благодарностью! :)

import math
def sieves(N): 
    x = 1000*[0]        
      prime = 2
      print('2')
      i = 3
      while (i <= N):
         if i not in x:
            print(i)
            prime += 1
            j = i
            while (j <= (N / i)):
               x.append(i * j)
               j += 1
         i += 2
      print("\n")
def main():
    count = 0
    for i in range (1000):
       count = count + 1
    print(sieves(math.sqrt(1000)))

main()

Answer 1

Кажется, проблема в строке j = i.Вы хотите начать с j = 1, чтобы вы перехватили все кратные i и добавили их в список не простых элементов "x".Если вы начнете J = I, вы будете скучать по некоторым.И когда вы проверяете «я не в х», он оценивается как истинный для некоторых не простых чисел.

Также вместо x.append (i * j) вы, вероятно, имели в виду x [i * j] = 1 (т. Е. Значение 1 означает, что i * j == не является простым) С этой модификацией «я не в x"может быть оптимизировано до" x [i] == 0 ", нет причин искать во всем массиве.Это было бы намного эффективнее, чем сохранение разреженного массива "x" и необходимость поиска его элементов на каждом этапе цикла.