en algoritme om dagen: Sådan kontrolleres et primtal i JavaScript

Marina Shemesh
Marina Shemesh

Følg

maj 28, 2020 * 7 min læst

det er næsten garanteret, at du på et tidspunkt i din kodningsuddannelse bliver bedt om at skrive en form for funktion, der involverer primtal. Det er en populær øvelse i kodning boot camps og nogle gange endda pop op i jobsamtaler.

Hvad er primtal?

et primtal er et naturligt tal større end 1, hvis eneste faktorer er 1 og selve tallet. Det vil sige, det kan kun deles ligeligt med 1 og sig selv.

naturlige tal er positive heltal såsom 1, 5, 201, 229999 osv. Tallet 0, brøker, decimaler og negative tal er ikke naturlige tal.

tallet 5 er et primtal, fordi dets eneste faktorer er 1 og 5. Der er ingen anden måde at ‘oprette’ nummer 5.

tallet 4 er ikke et primtal, fordi 2 gange 2 også giver os 4.

tallet 20 er ikke et primtal, fordi 5 gange 4 også giver os 20, såvel som 2 gange 10.

primtal er aldrig lige (undtagen 2)

en af de hurtigste måder at kontrollere, om et tal er et primtal eller ej, er at kontrollere, om det er et lige tal. Hvis et tal kan divideres med 2 uden at efterlade en rest, opfylder det ikke længere definitionen for et primtal — et tal, der kun kan deles ligeligt med 1 og sig selv.

i JavaScript kan vi kontrollere for lige tal ved hjælp af modulo-operatøren (%).

modulo-operatoren returnerer resten, efter at et heltal er divideret med et andet.
for eksempel giver 12% 5 2.
og 59% 5 giver 4.

hvis du deler et heltal med 2, og resten er 0, ved vi, at heltal er et lige tal.

for eksempel 10% 2 = 0
og 2200 % 2 = 0

i JavaScript vil det se sådan ud:
num % 2 === 0

så lad os begynde at oprette vores JavaScript-funktion for at kontrollere, om et tal er et primtal eller ej:

function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

Husk, at 2 er et primtal

funktionen ovenfor vil dog også angive, at 2 ikke er et primtal, så vi bliver nødt til at omskrive vores funktion. Vi kan også tage os af andre heltal, der ikke er hele tal som 0 og negative tal.

function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

nøgleordet ‘return’ signalerer en udgang fra funktionen, når den støder på en erklæring, der er sand. Hvis tallet er 2, stopper funktionen ved den anden linje:

if (num === 2) return true;

du kan finde en stor liste over kendte primtal her for at hjælpe dig med at kontrollere funktionen.
ikke alle ujævne tal er primtal

denne funktion fungerer okay til at kontrollere, om et tal er jævnt eller ej, men mislykkes med ujævne tal som 9 og 27, der ikke er primtal.

vi bliver nødt til at kontrollere, om parameteren kan opdeles i andre faktorer (undtagen 1, sig selv og 2) uden at efterlade en rest. Tallet 9 kan for eksempel også divideres med 3.

vi gør dette ved at gøre brug af en for loop, hvor parameteren ved hver iteration divideres med en anden loop-variabel. Sløjfen fortsætter med at køre, indtil der ikke er nogen rester, eller der ikke er flere loopvariabler tilgængelige.

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

funktionen holder looping og kontrol for remainders. Ved hver iteration divideres argumentet med en ny loop-variabel, og resten kontrolleres. Hvis resten er 0, betyder det, at argumentet er helt deleligt med et andet tal end sig selv og ikke er et primtal.

side note: Hvad er forskellen mellem en parameter og et argument?
parametre er de variabler, der bruges som en del af funktionsdefinitionen. For eksempel er num i funktion isPrime(num) parameteren.

argumenter er de værdier, der overføres til funktionen, når den påberåbes. For eksempel
tallet 9 i isPrime(9) er argumentet.

hvis der er en rest, gentager funktionen igen, indtil den når grænsen ved

 i < num

når den endelige iteration er nået, og der stadig er en Rest tilbage, er argumentet et primtal, og funktionen stopper.
vi slutter med en loop-variabel, der er et tal mindre end parameteren, fordi vi ikke er interesserede i faktorer, der er større end argumentet.

en hurtig demonstration

lad os demonstrere dette med primtal på 5.

function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}

første sløjfe:
1. i = 2 og 2 <5, så vi fortsætter med sløjfen
2. 5% 2 giver en rest, så vi ikke forlader sløjfen, men fortsætter med i++

anden sløjfe:
1. i = 3 og 3 <5, så vi fortsætter med sløjfen
2. 5% 3 giver en rest, så vi ikke forlader sløjfen, men fortsætter med i++

tredje sløjfe:
1. i = 4 og 4 < 5, og vi har nået slutningen af sløjfen, fordi 5 ikke er <end 5
2. 5% 4 giver en rest. Dette betyder, at tallet 5 er et primtal

ved hjælp af firkantede rødder med større primtal

primtal eskalerer hurtigt til enorme tal. Dette betyder, at vores For loop fortsætter med at gentage fra den ene loop-variabel til den næste i adskillige gange.

vi kan forkorte processen ved at bruge kvadratroden af en parameter. En kvadratrod af et heltal er det tal, der blev ganget med sig selv for at oprette et produkt.

kvadratroden af 81 er 9, fordi 9 gange 9 = 81.

i stedet for at gentage fra 2 til 80 for at kontrollere, om der er nogen rester tilbage eller ej, kan vi bare gentage op til og med 9, kvadratroden af 81.
9% 9 = 0, hvilket betyder, at 81 ikke er et primtal.
dette giver mening, fordi 9 gange 9 er faktorer på 81, hvilket betyder, at det ikke overholder definitionen af et primtal — et tal, der kun kan deles ligeligt af sig selv og 1.

i JavaScript kan du finde kvadratroden af et tal ved hjælp af matematik.Square. Vi skriver det sådan:

Math.sqrt(num);

lad os bruge det i Vores funktion, der kontrollerer, om et tal er et primtal:

function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

Hvorfor er primtal så nyttige?

i kontakt, science fiction-bogen af Carl Sagan, sender udlændinge en lang række primtal som bevis for, at deres budskab er fra en intelligent livskraft. Vi kommunikerer ikke (endnu) med udenjordiske via primtal, men bruger dem på forskellige måder lige her på planeten Jorden.

cikader dukker op synkroniseret i nøjagtige primtalcykler. De uregelmæssige cyklusser betyder, at ingen rovdyr har udviklet sig til at leve af disse insekter. Det faktum, at de alle kommer ud af jorden til tiden, øger også individets chance for at overleve.

skærme bruger primtal til at definere farveintensiteter af billedpunkter. De bruges også i værktøjsfremstilling for at slippe af med harmonier. To gear, der deler et multiplum, vil engagere de samme tænder igen og igen, hvilket fører til et ujævnt Slidmønster. Gear, der har et primtal af tænder på deres tandhjul vil vare længere.

primtal er dog mest i moderne computersikkerhed. Det er ikke så svært at finde store primtal, men det er meget vanskeligt at indregne store tal i primtal.

det er let at finde ud af, at 27 er 3 gange 3 gange 3, men det er meget sværere at finde ud af, at 2.244.354 er 2 gange 3 gange 7 gange 53.437. Og 2.244.354 er ikke engang så stort et tal. At finde de primære faktorer er teknisk set et spørgsmål om tid, men fordi det vil tage så lang tid, siger vi, at det ikke kan gøres.

moderne krypteringsalgoritmer bruger det faktum, at der endnu ikke er nogen computer, der kan tage et super-stort antal og hurtigt finde ud af, hvilke primtal der gik i at gøre det.

du kan handle online eller sende en krypteret besked via en app på din telefon, men et eller andet sted hjælper primtal dig med at holde dine hemmeligheder sikre.

her er tre flere links til andre” en algoritme om dagen ” artikler:

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.