Подсчитайте простые результаты полинома

Может ли кто-нибудь помочь мне и сказать мне, почему это не работает? Цель состоит в том, чтобы подсчитать количество простых чисел, полученных данным многочленом для входных данных n в указанном диапазоне [a,b]:

    def count_primes(poly, a, b):
    primes = 0
    if b >= a:
        for n in range(a, b):
            result = poly(n)
            if result > 1:
                for i in range(2, result):
                    if (result % i) == 0:
                        break
                    else:
                        primes += 1
            else:
                break
    return primes


def poly(n):
    return n**2 + n + 41


print(count_primes(poly, 0, 39))

В этом случае результат должен возвращать 40.

[2] Проблема Решение Шаг-1. Возьмите число, которое нужно проверить, и сохраните его в переменной. Шаг 2. Присвойте переменной count значение 0. Шаг 3. Пусть цикл for находится в диапазоне от 2 до половины числа (исключая 1 и само число). Шаг-4. Затем найдите количество делителей с помощью оператора if и каждый раз увеличивайте переменную count. Шаг-5. Если число делителей меньше или равно 0, то число простое. Шаг-6. Распечатайте окончательный результат. Шаг-7. Выход.


python polynomials primes
person Kajice    schedule 29.10.2019    source источник
comment
Ваш код считает, что 7 считается 5 простыми числами, по одному для каждого проверенного делителя, на который он не делится.   -  person user2357112 supports Monica    schedule 29.10.2019
comment
Обратите внимание, что просеивание работает с любой полиномиальной конгруэнтностью. То есть p(x + kN) = p(x) mod N, если p(x) — полином от x с целыми коэффициентами. Воспользовавшись этим преимуществом, вы можете значительно сэкономить время, если b-a велико или если a очень велико.   -  person President James K. Polk    schedule 29.10.2019

Ответы (3)


arrow_upward
1
arrow_downward

Проблема в том, что предложение else во вложенном цикле относится к if, тогда как его следует активировать только в том случае, если цикл завершился без break. Просто измените идентификатор на:

if result > 1:
    for i in range(2, result):
        if (result % i) == 0:
            break
    else:
        primes += 1
person Aryerez    schedule 29.10.2019

arrow_upward
1
arrow_downward

Это неправильный способ подсчета простых чисел:

        if result > 1:
            for i in range(2, result):
                if (result % i) == 0:
                    break
                else:
                    primes += 1

Должно быть:

        if result > 1:
            isPrime = True
            for i in range(2, result):
                if (result % i) == 0:
                    isPrime = False
                    break
            if isPrime:
                primes += 1

Кроме того, это само собой разумеется. Простая оптимизация для обнаружения простых чисел. Вам нужно только проверить делимость на делимость с 2 и всеми нечетными числами между 3 и sqrt (результат).

person selbie    schedule 29.10.2019
comment
Кстати, for ... else ... может быть лучшим выбором. - person lincr; 29.10.2019
comment
Просто отметим: в Python 3.8 теперь есть функция math.isqrt(), которая возвращает целую часть квадратного корня. - person Aivar Paalberg; 29.10.2019

arrow_upward
0
arrow_downward 

def count_primes(poly, a, b):
    primes = 0
    if b >= a:
        for n in range(a, b+1):
            result = poly(n)
            if result > 1:
                for i in range(2, result):
                    if (result % i) == 0:
                        break
                else:
                    primes += 1
            else:
                break
    return primes


def poly(n):
    return n**2 + n + 41


print(count_primes(poly, 0, 39))

Проблемы:

  1. вы делаете primes += 1 слишком рано. В ваших методах вы должны проверять до тех пор, пока не произойдет невозможное деление, а затем выполните сложение.

  2. [a, b] Обе конечные точки включены. Затем вы должны использовать b+1 в своем for n in range(a, b+1), который производит 40.

person lincr    schedule 29.10.2019