Неопределённая ошибка в тесте на Кармайкловы числа

Рейтинг: 1Ответов: 1Опубликовано: 04.08.2023

Никак ни могу понять где ошибка в коде, все вроде выходит из определения чисел Кармайкла, но тем не менее программа их не видит.

k = int(input())


def is_prime(x):
    for j in range(2, x // 2 + 1):
        if x % j == 0:
            return False
    return True


def is_fermat_prime(x):
    for q in range(2, x):
        if q ** (x - 1) % x != 1:
            return False
    return True


def is_carmichael(x):
    if is_prime(x) is False & is_fermat_prime(x) is True:
        return True
    else:
        return False


exit = []
for i in range(2, k):
    if is_carmichael(i) is True:
        exit.append(i)

print(exit)

Я проверял правильность написания функций is_prime и is_fermat_prime, ошибка вероятнее всего в is_fermat_prime.

python теория-чисел
Источник: Stack Overflow на русском

Ответы

▲ 2

Проблемы

  1. Число Кармайкла - составное n, которое удовлетворяет сравнению bn-1 ≡ 1 (mod n) для всех целых b, взаимно простых с n.

    В вашем коде нет проверки взаимной простоты.

  2. Выражение is_prime(x) is False & is_fermat_prime(x) is True вычисляется не так как вы ожидаете.

    Например False is False & True is True вычисляется в False. Потому что приоритет & выше чем приоритет is (см. таблицу приоритетов). После расстановки скобок получится False is (False & True) is True → False is False is True. Компилятор Питона транслирует такие выражения аналогично 10 < x < 20 и превращает его в (False is False) and (False is True), который вычисляется в True and False → False.

    Поправить можно, расставив скобки: (is_prime(x) is False) & (is_fermat_prime(x) is True).

    Но и у этого выражения есть свои проблемы. & медленно обрабатывает логические значения - правая часть вычисляется даже если левая уже вернула False, and этого не делает, существенно экономя время на вызове is_fermat_prime.

    Операторы is вообще в нормальном коде не должны встречаться. Лучше написать not is_prime(x) and is_fermat_prime(x).

После исправления код заработает. Чтобы работало быстрее, проверку на простоту делайте до корня из x а для вычисления степени по модулю используйте pow. У неё есть третий параметр - модуль.

Теорема Корсельта

составное число n является числом Кармайкла тогда и только тогда, когда n свободно от квадратов и для каждого простого делителя p числа n число p - 1 делит n - 1.

Можно искать числа Кармайкла по их разложению на простые.

import math


def factors(n):
    if n % 2 == 0:
        e = 0
        while n % 2 == 0:
            n //= 2
            e += 1
        yield 2, e

    i = 3

    n_sqrt = math.isqrt(n)
    while i <= n_sqrt:
        if n % i == 0:
            e = 0
            while n % i == 0:
                n //= i
                e += 1
            yield i, e
            n_sqrt = math.isqrt(n)
        i += 2

    if n > 1:
        yield n, 1


def is_carmichael(n):
    for p, e in factors(n):

        # free of squares
        if e > 1:
            return False

        # divisibility
        if (n - 1) % (p - 1) != 0:
            return False

    # is not prime?
    return p != n


def main():
    for n in range(2, int(input())):
        if is_carmichael(n):
            print(n)


main()

За шесть секунд программа находит 43 числа Кармайкла до миллиона:

$ time echo 1000000 | python korselt.py | wc -l
43

real  0m5.152s
user  0m5.140s
sys   0m0.004s