Milyen képlet van a prímszámokra? Mármint ne a prím tényezőkre bontást mondjátok hanem valami egyenletet amivel pl meg lehet határozni 14.545.435.435.454 erről a számról hogy prím e vagy sem

"ne a prím tényezőkre bontást mondjátok"

Más nincs.

Ahogy #1 írja, lehet programot írni, ami elvégzi ezt helyetted.

Elméleti van:

Ha (n-1)! (!=faktoriális) osztható n-el akkor n nem prím egyébként az. De ez is oszthatóságon és prímtényezőkön alapul, továbbá a fenti faktort még egy szuperszámítógép se számolná ki azt hiszem...

produktum [i=2...n-1] n mod i = 0

Prímtényezőkre se kell bontani hozzá :)

Vannak prímtesztelő algoritmusok, melyek előszörre is kiszórják a 14.545.435.435.454 számot, hiszen páros, és kettőnél nagyobb.

Aztán elkezdik a prímtesztelést, aminek két eredménye lehet:

* A szám összetett.

* A szám valószínűleg prím.

A prímteszt során a számnak több prímteszten is át kell mennie:

[link]

Képlet, algoritmus nincs arra, hogy egy prímszámról megállapítsuk, hogy prím, illetve hogy generáljunk egy prímszámot, nyilván leszámítva a triviális, naiv eljárást, hogy végigpróbáljuk a szám gyökéig az összes prímet, hogy osztható-e vele, vagy pl. használjuk Eratoszthenész szitáját.

Viszont vannak mindenféle prímtesztek, amivel ha nem is 100%-os biztonsággal, de a kívánt valószínűséggel meg lehet állapítani egy számról, hogy prím-e. Lásd: [link] .

A mai kriptográfia – némi csavarral – pont azon alapszik, hogy két nagyon nap prím szorzatát ismerve hatalmas számítási kapacitást igényel, hogy megkapjuk a két prímet.