На основе теоремы Вильсона реализовать тест проверки числа на простоту

@zi_romanov · Регистрация: 08.04.2020

Author24 — интернет-сервис помощи студентам

Здравствуйте, прошу помощи

На основе теоремы Вильсона реализовать тест проверки числа на простоту, причем программа должна быстро отрабатывать при числах состоящих из 60 знаков.
Теорема Вильсона
Если p простое число, то формула(p-1)!+1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv$ 0 (mod p), где p>1
Проблема заключается в факториале, с числами в 60 знаков мой код будет работать оооочень долго, ниже код.
Прошу помочь с ускорением, чтобы с числами из 60 знаков считалось не очень долго

import time

Код

def fact(n):
    factorial = 1
    while n > 1:
        factorial *= n
        n -= 1
    return factorial
def wilson(p):
    k = 0
    start_time = time.time()
    if p > 1:
        k = (fact(p-1) + 1) % p
        if (k == 0):
            print("Вероятно простое")
            print("Затраченное время тестирования: %s секунд" % (time.time() - start_time))
        else:
            print("Составное")
            print("Затраченное время тестирования: %s секунд" % (time.time() - start_time))
def main():
        p = int(input("Введите целое число больше 1: "))
        if(p > 1):
            wilson(p)
        else:
            print("Вы ввели не корректное число")

main()

@mihailm · 04.11.2021, 23:51

Я думаю что речь идет о том чтобы в процессе работы программы получались числа не более чем 60-значные.
Факториалы 60-значных чисел это немножко многовато)
Так что ваша программа должна проверять на простоту числа до 47 (сорока семи).
Но длинную арифметику писать надо, не парьтесь, это просто

@zi_romanov · 04.11.2021, 23:53 **[ТС]**

В этом и соль, что надо именно проверить число с минимум 60 знаками и проверить его на простоту

@mihailm · 04.11.2021, 23:55

я написал в чем соль, сделайте это

@zi_romanov · 05.11.2021, 00:02 **[ТС]**

у меня спокойно проверяются числа и из восьми знаков, например, 12345678 - за 622 секунды и результат очевидно составное.
Этот результат не удовлетворяет по времени, слишком долго, да и число надо в 5 раз больше по количеству символов.
Какую функцию можно добавить для ускорения процесса?

@mihailm · 05.11.2021, 00:13

начните с маленьких чисел до 50, проверьте так, на всякий)

@zi_romanov · 05.11.2021, 00:15 **[ТС]**

Введите целое число больше 1: 47
Вероятно простое
Затраченное время тестирования: 0.00011801719665527344 секунд
Проверила

@Mc_RoSA · 06.11.2021, 14:35

Формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(p-1 \right)! + 1\equiv 0 \left(p \right)$ можно чуть оптимизировать, если учесть, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(p-1 \right)\equiv \left(-1 \right) \left(p \right)$ и так далее, то формула принимает вид $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\left(\frac{p-1}{2} \right)!}^{2}-1\equiv 0\left(p \right)$ . И тут уже перемножать не все числа, а только половину

Выше у меня ошибка

@palva · 07.11.2021, 13:26

zi_romanov,
Вам как бы намекнули, что не стоит пытаться вычислять факториал, при больших числах он не поместится на вашем крутом компьютере. Но факториал вам и не нужен, вам нужна проверка на его делимость на p. Поэтому находите остаток от деления после каждого умножения и на следующем цикле используйте этот остаток. Типа

Python

k = 1
for i in range(1, p):
    k = k * i % p
if (k == p - 1):
    print("Вероятно простое")

Код

Введите целое число больше 1: 12345701
Вероятно простое
Затраченное время тестирования: 3.960564374923706 секунд

Ну, у меня старинный ноутбук

Добавлено через 10 минут
Проверять на делимость можно внутри цикла, тогда вычисления ускорятся в случае составного p. (А в случае простого немного замедлятся.)
Наверно, еще можно как-то ускорить.

@zi_romanov 0 / 0 / 0 Регистрация: 08.04.2020 Сообщений: 17
		1
	На основе теоремы Вильсона реализовать тест проверки числа на простоту 04.11.2021, 23:41. Показов 1323. Ответов 8 Метки информатика студент, теория чисел (Все метки) Здравствуйте, прошу помощи На основе теоремы Вильсона реализовать тест проверки числа на простоту, причем программа должна быстро отрабатывать при числах состоящих из 60 знаков. Теорема Вильсона Если p простое число, то формула(p-1)!+1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv$ 0 (mod p), где p>1 Проблема заключается в факториале, с числами в 60 знаков мой код будет работать оооочень долго, ниже код. Прошу помочь с ускорением, чтобы с числами из 60 знаков считалось не очень долго import time Код def fact(n): factorial = 1 while n > 1: factorial *= n n -= 1 return factorial def wilson(p): k = 0 start_time = time.time() if p > 1: k = (fact(p-1) + 1) % p if (k == 0): print("Вероятно простое") print("Затраченное время тестирования: %s секунд" % (time.time() - start_time)) else: print("Составное") print("Затраченное время тестирования: %s секунд" % (time.time() - start_time)) def main(): p = int(input("Введите целое число больше 1: ")) if(p > 1): wilson(p) else: print("Вы ввели не корректное число") main() 0

@mihailm 1666 / 1106 / 294 Регистрация: 05.10.2014 Сообщений: 5,402
	04.11.2021, 23:51	2
	Я думаю что речь идет о том чтобы в процессе работы программы получались числа не более чем 60-значные. Факториалы 60-значных чисел это немножко многовато) Так что ваша программа должна проверять на простоту числа до 47 (сорока семи). Но длинную арифметику писать надо, не парьтесь, это просто 0

@zi_romanov 0 / 0 / 0 Регистрация: 08.04.2020 Сообщений: 17
	04.11.2021, 23:53 [ТС]	3
	В этом и соль, что надо именно проверить число с минимум 60 знаками и проверить его на простоту 0

@mihailm 1666 / 1106 / 294 Регистрация: 05.10.2014 Сообщений: 5,402
	04.11.2021, 23:55	4
	я написал в чем соль, сделайте это 0

@zi_romanov 0 / 0 / 0 Регистрация: 08.04.2020 Сообщений: 17
	05.11.2021, 00:02 [ТС]	5
	у меня спокойно проверяются числа и из восьми знаков, например, 12345678 - за 622 секунды и результат очевидно составное. Этот результат не удовлетворяет по времени, слишком долго, да и число надо в 5 раз больше по количеству символов. Какую функцию можно добавить для ускорения процесса? 0

@mihailm 1666 / 1106 / 294 Регистрация: 05.10.2014 Сообщений: 5,402
	05.11.2021, 00:13	6
	начните с маленьких чисел до 50, проверьте так, на всякий) 0

@zi_romanov 0 / 0 / 0 Регистрация: 08.04.2020 Сообщений: 17
	05.11.2021, 00:15 [ТС]	7
	Введите целое число больше 1: 47 Вероятно простое Затраченное время тестирования: 0.00011801719665527344 секунд Проверила 0

@Mc_RoSA 13 / 11 / 4 Регистрация: 10.01.2020 Сообщений: 71
	06.11.2021, 14:35	8
	Формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(p-1 \right)! + 1\equiv 0 \left(p \right)$ можно чуть оптимизировать, если учесть, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(p-1 \right)\equiv \left(-1 \right) \left(p \right)$ и так далее, то формула принимает вид $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\left(\frac{p-1}{2} \right)!}^{2}-1\equiv 0\left(p \right)$ . И тут уже перемножать не все числа, а только половину Выше у меня ошибка Миниатюры 0

	07.11.2021, 13:26

На основе теоремы Вильсона реализовать тест проверки числа на простоту

Решение