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

@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

Code    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
k = 1
for i in range(1, p):
    k = k * i % p
if (k == p - 1):
    print("Вероятно простое")

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

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

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

Новые блоги и статьи Все статьи Все блоги /
TypeScript: Интерфейсы vs Типы run.dev 11.04.2025 Современная разработка на JavaScript сталкивается с множеством проблем при масштабировании проектов. Типизация кода стала хорошим инструментом, помогающим избежать ошибок во время выполнения,. . .	Управление топиками и разделами Kafka Javaican 11.04.2025 Apache Kafka — распределенная платформа потоковой передачи данных, которая стала стандартом для построения высоконагруженных систем обмена сообщениями. В современной архитектуре микросервисов,. . .	Миграция монолита в Event-Driven микросервисную архитектуру на C# stackOverflow 11.04.2025 Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .	Go в Kubernetes: Управление ресурсами golander 11.04.2025 Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .	Агрегаты и сущности в DDD микросервисах Javaican 10.04.2025 Разработка современных программных систем часто приводит на распутье: монолит или микросервисы? Даже при выборе микросервисной архитектуры многие команды сталкиваются с проблемой правильного. . .
Многопоточность в C#: Task и параллельное программирование UnmanagedCoder 10.04.2025 Современные процессоры уже давно перестали наращивать тактовую частоту в пользу увеличения количества ядер. Это создало интересную ситуацию: разработчики, привыкшие к последовательному. . .	Линейное решение нелинейной задачи с помощью арктангенса для метода обработки данных из double buffering. Hrethgir 10.04.2025 Публикация в доработке, метод арктангенса в комментариях внизу. Вообще изначально я пренебрёг квадратурой числа, но потом понял, что для вычисления приблизительного значения - сгодится, формулу. . .	Переменные в Python py-thonny 10.04.2025 Переменная в программировании — это символическое имя, связанное с областью памяти, в которой хранится значение. Она позволяет получать доступ к данным через понятные человеку идентификаторы, а не. . .	Многопоточность в C#: Task и асинхронные операции UnmanagedCoder 10.04.2025 Многопоточность позволяет выполнять несколько операций одновременно, что важно для решения двух основных задач: повышения скорости выполнения вычислительно-сложных операций и сохранения отзывчивости. . .	Запуск контейнеров Docker на ARM64 Mr. Docker 09.04.2025 Появление таких решений, как Apple M1/ M2, AWS Graviton, Ampere Altra и Raspberry Pi, сделало использование ARM-систем обыденностью для многих разработчиков и DevOps-инженеров. При этом Docker,. . .

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

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

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

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

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

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

@Mc_RoSA 13 / 11 / 4 Регистрация: 10.01.2020 Сообщений: 71
	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)$ . И тут уже перемножать не все числа, а только половину Выше у меня ошибка Миниатюры 0

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

Решение