Názor k článku Objeveno nové nejvyšší prvočíslo. Má skoro 25 milionů číslic od Kaz - Protože to deterministicky ověřit není vůbec sranda. Deterministické...

Protože to deterministicky ověřit není vůbec sranda. Deterministické algoritmy mají velkou složitost a nedeterministické nemusí vždy fungovat na 100%. Nejjednodušší, ale časově nepoužitelné řešení, je zkoušet dané číslo dělit všemi prvočísly až do velikosti druhé odmocniny testovaného čísla. Spočítej si, kolik toho při testu čísla o délce 25 milionů číslic bude.
Podívej se zde https://www.wikihow.cz/Jak-zjistit,-zda-je-%C4%8D%C3%ADslo-prvo%C4%8D%C3%ADslem nebo https://math.feld.cvut.cz/gollova/mkr/mkr9.pdf.