Python находит простые числа между любыми двумя числами

Я пытаюсь найти простые числа между любыми двумя случайными числами.

Во-первых, я написал такой код:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, i):
        if i%j == 0:
            break
    else:
        print i,

Теперь для тестового примера предположим, что я ввожу 2, 30, затем он печатает

2 3 5 7 11 13 17 19 23 29

Теперь анализируя, нам не нужно зацикливаться до «i» во втором цикле, скорее мы можем сделать то же самое, зациклившись до i/2, затем я изменил код следующим образом:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, int(i/2)+1):
        if i%j == 0:
            break
    else:
        print i,

Тогда результат будет таким же, как и выше, пока мы зацикливались до i/2 во втором цикле.

Теперь я пытаюсь использовать метод решета Эратосфена для печати простых чисел, и я использовал код как:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    sqrt_num = int(n**(0.5))
    for j in range(2, sqrt_num+1):
        if i%j == 0:
            break
    else:
        print i,

но он печатает

7 11 13 17 19 23 29

для того же входа.

Пожалуйста, помогите мне понять, что я делаю неправильно. И как я могу сделать то же самое, используя этот метод.


python primes sieve-of-eratosthenes
person Ashvini Maurya    schedule 15.07.2016    source источник
comment
Вы тестировали свой код в диапазоне чисел, например [24..28]?   -  person rossum    schedule 16.07.2016
comment
Да, он не печатает никаких чисел, потому что в [24..28] нет простых чисел.   -  person Ashvini Maurya    schedule 16.07.2016

Ответы (1)


arrow_upward
2
arrow_downward

Ваш внутренний цикл зацикливался до i-1 или i/2. Этот внутренний цикл был коротким, когда i был маленьким, и длиннее, когда i стал больше.

Теперь ваш внутренний цикл достигает sqrt_num, что является константой, вычисляемой из n. Разница в поведении.

Рассмотрим i = 3, внутренний цикл проходит от j = 2 до j = 5 и найдет случай, когда i%j == 0... в частности, когда j == 3.

Чтобы было ясно: проблема в "sqrt_num, которая является константой". Измените его на квадратный корень из внешнего индекса, i.

    sqrt_num = int(i**(0.5))
person AJNeufeld    schedule 15.07.2016
comment
Да, вы правы, но как я могу заставить работать как положено. - person Ashvini Maurya; 16.07.2016