Primtal faktorer
I januari 2013 var det största kända primtalet ett så kallat Mersenneprimtal med
17 425 170 siffror.
Hur stora faktorer (antal siffror) måste man kontrollera med för att veta att talet är ett primtal?
Hur låser man en sån uppgift?
Jag trodde att man skulle bara dra ruten ur talet så får man hur antal siffror om måste kontrollera
Du tänker rätt - fast du får ju största tänkbara faktorn inte antalet siffror i den.
Så det är bara att dra roten ur
Det är inte angivet om basen är tio eller två eller något annat.
Vi antar att det är bas tio. Och att ifrågavarande primtal är p.
Det betyder att 1017425169 < p < 1017425170
Av uppgiften framgår inte var i intervallet talet ligger. Notera att nio tiondelar av de positiva heltalen under den övre gränsen ligger över den undre gränsen, så det spelar ganska stor roll (för den som vill kolla) var p är.
Här får vi utgå från den övre gränsen. Vi tar roten ur 1017425170 som är 108712585 = q, säg. Om vi vet att inget tal ≤ q är faktor i p, så är p ett primtal. Så det största talet vi kan behöva testa är q = 1000…000 (en etta och 8712585 nollor) som har 8712585+1 siffror. Men vid närmare eftertanke kommer vi inte behöva testa q eftersom q2 > p.
Så min slutsats är att den minsta faktorn i p – innan vi testat – skulle kunna ha 8 712 585 siffror men inte fler.
Anm. I Wiki anges det största kända Mersenneprimtalet till p = 282 589 933 – 1 (rekordet satt 7 dec 2018). Den uppgiften ger möjlighet till en betydligt exaktare bestämning av q.
