Udskriv primtal
Et helt tal større end 1 kaldes et primtal, hvis det ikke kan deles uden rest af noget andet end 1 og sig selv.
Med andre ord er n > 1 et primtal, hvis det ikke kan deles jævnt af noget andet end 1 og n.
For eksempel er 5 et primtal, fordi det ikke kan deles uden rest af 2, 3 og 4.
Skriv koden, der udskriver primtal i intervallet fra 2 til n.
For n = 10 vil resultatet være 2,3,5,7.
P.S. Koden skal fungere for enhver n, ikke være ‘hard coded’ til en bestemt værdi.
Der er mange algoritmer til denne opgave.
Lad os bruge en indlejret løkke:
For hvert i i intervallet {
tjek om i har en divisor fra 1..i
hvis ja => værdien er ikke et primtal
hvis nej => værdien er et primtal, vis det
}Koden med en label:
let n = 10;
nextPrime:
for (let i = 2; i <= n; i++) { // for hvert i...
for (let j = 2; j < i; j++) { // tjek for en divisor..
if (i % j == 0) continue nextPrime; // ikke et primtal, gå til næste i
}
alert( i ); // et primtal
}Der er meget plads til optimering. For eksempel kunne vi lede efter divisorer fra 2 til kvadratroden af i. Men uanset hvad, hvis vi vil være virkelig effektive for store intervaller, skal vi ændre tilgangen og stole på avanceret matematik og komplekse algoritmer som Quadratic sieve, General number field sieve osv.