Názory k článku Objeveno nové nejvyšší prvočíslo. Má skoro 25 milionů číslic

"Prohlásit objevení nejvyššího prvočísla se proto neobejde bez zdlouhavého ověření, zdali číslo opravdu není beze zbytku dělitelné."

To se nemusí moc dlouho ověřovat... Každý by měl vědět, že každé přirozené číslo je beze zbytku dělitelné... Jedničkou a samo sebou...

Taková velka prvocisla by mohla vychazet i knizne :-)

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.

Pro jistotu - složitostí samozřejmě myslím asymptotickou časovou složitost daného algoritmu, nikoli jak je komplikovaný na programování :-).

Já vím, jak se ověřuje prvočíselnost... Ale autor článku píše, že se ověřuje nikoliv prvočíselnost, ale "zdali číslo opravdu není beze zbytku dělitelné". Narážím na formální nepřesnost takového tvrzení. Jednak dělitelnost je vždy "čeho" a "čím" a není definovaná sama osobě, druhak je potřeba ověřovat "nedělitelnost" pouze jak bylo zmíněno prvočísly menšími nebo rovnými odmocnině z potvrzovaného čísla...

Pokud by to bylo, jak píše autor článku, žádné prvočíslo by neexistovalo, protože každé přirozené číslo je dělitelné přinejmenším jedničkou a samo sebou (bez újmy na obecnosti i jednička, pro kterou jsou tato dvě čísla rovna...). Nic by se pak ověřovat nemuselo, triviálně by se řeklo, že číslo je dělitelné a konec.

Tak to se omlouvám, to jsem z toho Tvého příspěvku nepochopil.