Test om ett tal är ett primtal
Hej,
Jag har en fråga om primtal. När man undersöker om ett tal a är ett primtal, så vet jag att det räcker med att testa med alla primtal som är lika med eller mindre än , och se om någon av dem är en positiv delare.
Hittar man ett primtal b som är en positiv delare och uppfyller
2 b <
så är talet a inget primtal. Hittar man det ej så är a ett primtal.
Jag skulle gärna vilja ha hjälp hur jag ska tänka för att lista ut varför det är så, alltså varför räcker det med att undersöka primtal som är lika med eller mindre än ? Kan jag få en ledtråd?
Faktorer kommer ju alltid i par, och om den ena faktorn är större än måste ju den andra vara mindre för att svaret ska bli . Då borde man ju redan ha hittat den mindre faktorn, och om det inte finns någon mindre faktor kan man konstatera att det inte heller finns någon större faktor.
Tusen tack! Det var mycket bra förklarat!