EigenraumZuerst berechnet man
612! = 612 x 611 x … x 2 x 1 = …
2/6
3134528403143108701972672299461418332296837343246716585684044707445890749945478965933760638115160687756144747746937908065119655738453423861650511230777959924500058849607438611956751928685383556149800233518653016194360474023387773604331338823981095407232169751495648396227741789863007596304690724644602646108037752754540735716182761064342523652986258592044516578675003577724678382930114041128654477760574003514346226686369230547168931856597924435316922950557312378843058423701997683554276615…
3/6
4558798759664379979952541373840166288556021872652020619480545035294925941222688535043037956813911652953457848522327113779703167879718804691421684687833976135356532017918993728545021619559739061229675255398587742320725277601036551546829311028572503158470998552383207269924186459902156555062736692600239147192251083571542826346955487602642394541630869850262848486397035978836945713050686757941502520618916378341773341247135879277972891272991647263418360988603569457605183086016267392013085308…
4/6
835518643480752186428220313183859284078305373926464731934724610436242021632357819237253327307967453646837211022874404127196544738009403131145645951123117760186538479875020348989844587803562422601690116503526689991751870811277858322725454215426434126714574629250308831423366022422657889634282469670449044065878016000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
5/6
Jetzt nimmt man den Rest modulo 613 und erhält:
612! mod 613 = 612
🤔
Also ist 613 prim. Das ist der Satz von Wilson, der sagt, dass eine Zahl n genau dann prim ist, wenn (n-1)! kongruent zu n-1 modulo n ist.
6/6
Stefan Müller 
612! ist aber ganz schön viel. Kommt man da mit diesem Sieb nicht schneller hin?
Pfff.. da fällt bestimmt was durch.
Interessanterweise kann man in polynomieller Zeit testen, ob eine Zahl prim ist — aber wahrscheinlich nicht die Primfaktorzerlegung berechnen.
Ersteres war ein Durchbruch in meiner Studienzeit: https://en.m.wikipedia.org/wiki/AKS_primality_test
Zweiteres ist die Grundlage von viel aktueller Kryptographie. 🔐