Een algoritme een dag : Hoe om te controleren voor een priemgetal in JavaScript

Marina Semes
Marina Semes

Volg

28 Mei 2020 · 7 min lezen

Het is bijna gegarandeerd dat op een bepaald moment in uw codering onderwijs, zal u worden gevraagd om te schrijven wat het type van de functie waarbij de priemgetallen. Het is een populaire oefening in het coderen van bootcamps en soms zelfs pop-up in sollicitatiegesprekken.

wat zijn priemgetallen?

een priemgetal is een natuurlijk getal groter dan 1, waarvan de enige factoren 1 zijn en het getal zelf. Dat wil zeggen, het kan alleen gelijk worden verdeeld door 1 en zichzelf.

natuurlijke getallen zijn positieve gehele getallen zoals 1, 5, 201, 229999 enz. Het getal 0, breuken, decimalen en negatieve getallen zijn geen natuurlijke getallen.

het getal 5 is een priemgetal omdat de enige factoren 1 en 5 zijn. Er is geen andere manier om het getal 5 te ‘creëren’.

het getal 4 is geen priemgetal omdat 2 x 2 ons ook 4 geeft.

het getal 20 is geen priemgetal omdat 5 x 4 ons ook 20 geeft, evenals 2 x 10.

priemgetallen zijn nooit even (behalve voor 2)

een van de snelste manieren om te controleren of een getal een priemgetal is of niet is om te controleren of het een even getal is. Als een getal gedeeld kan worden door 2 Zonder een rest achter te laten, voldoet het niet meer aan de definitie voor een priemgetal — een getal dat alleen gelijk gedeeld kan worden door 1 en zichzelf.

in JavaScript kunnen we even getallen controleren met behulp van de Modulo operator (%).

de Modulo-operator geeft de rest terug nadat een geheel getal door een ander is gedeeld.
bijvoorbeeld 12% 5 geeft 2 terug.
en 59% 5 geeft 4 terug.

als je een geheel getal deelt door 2 en de rest is 0, weten we dat het gehele getal een even getal is.

bijvoorbeeld 10% 2 = 0
en 2200 % 2 = 0

in JavaScript zal het er ongeveer zo uitzien:
num % 2 === 0

dus laten we beginnen met het maken van onze JavaScript-functie om te controleren of een getal een priemgetal is of niet:

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

onthoud dat 2 een priemgetal

is de functie hierboven zal echter ook aangeven dat 2 geen priemgetal is, dus we zullen onze functie moeten herschrijven. We kunnen ook zorgen voor andere gehele getallen die geen hele getallen zijn, zoals 0 en negatieve getallen.

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

het trefwoord ‘return’ signaleert een uitgang van de functie wanneer het een statement tegenkomt dat waar is. Als het nummer 2 is, stopt de functie bij de tweede regel:

if (num === 2) return true;

u kunt hier een grote lijst met bekende priemgetallen vinden om u te helpen de functie te controleren.
niet alle oneven getallen zijn priemgetallen

deze functie werkt goed om te controleren of een getal even is of niet, maar faalt met oneven getallen zoals 9 en 27 die geen priemgetallen zijn.

we zullen moeten controleren of de parameter kan worden onderverdeeld in andere factoren (behalve 1, zichzelf en 2) Zonder een Rest over te laten. Het getal 9 bijvoorbeeld kan ook gedeeld worden door 3.

we doen dit door gebruik te maken van een for-lus waarbij bij elke iteratie de parameter wordt gedeeld door een andere lusvariabele. De lus blijft lopen totdat er geen restanten zijn of er geen lusvariabelen meer beschikbaar zijn.

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

de functie houdt looping en controle op restanten. Bij elke iteratie wordt het argument gedeeld door een nieuwe lus variabele en de rest wordt gecontroleerd. Als de rest 0 is, betekent dit dat het argument volledig deelbaar is door een ander getal dan zichzelf en geen priemgetal is.

kanttekening: Wat is het verschil tussen een parameter en een argument?
Parameters zijn de variabelen die worden gebruikt als onderdeel van de functiedefinitie. Bijvoorbeeld de num in functie isPrime (num) is de parameter.

argumenten zijn de waarden die aan de functie worden doorgegeven wanneer deze wordt aangeroepen. Bijvoorbeeld
het getal 9 in isPrime (9) is het argument.

als er een rest is, itereert de functie opnieuw totdat de limiet op

 i < num

bereikt is wanneer de laatste iteratie is bereikt en er nog een Rest overblijft, is het argument een priemgetal en stopt de functie.
we eindigen met een lusvariabele die één getal kleiner is dan de parameter omdat we niet geïnteresseerd zijn in factoren die groter zijn dan het argument.

een snelle demonstratie

laten we dit demonstreren met het priemgetal van 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;}

eerste lus:
1. i = 2 en 2 < 5, dus we gaan verder met de lus
2. 5 % 2 geeft een rest dus we verlaten de lus niet maar gaan door met i++

tweede lus:
1. i = 3 en 3 < 5, dus we gaan verder met de lus
2. 5% 3 geeft een rest dus we verlaten de lus niet maar gaan verder met i++

derde lus:
1. i = 4 en 4 < 5, en we hebben het einde van de lus bereikt omdat 5 niet < is dan 5
2. 5% 4 geeft een Rest. Dit betekent dat het getal 5 een priemgetal

is, waarbij gebruik wordt gemaakt van vierkantswortels met grotere priemgetallen

priemgetallen escaleren snel tot enorme getallen. Dit betekent dat onze for loop blijft herhalen van de ene lus variabele naar de volgende voor vele malen.

we kunnen het proces inkorten door de vierkantswortel van een parameter te gebruiken. Een vierkantswortel van een geheel getal is het getal dat met zichzelf werd vermenigvuldigd om een product te creëren.

de vierkantswortel van 81 is 9 omdat 9 x 9 = 81.

in plaats van 2 tot 80 te herhalen om te controleren of er nog restanten over zijn of niet, kunnen we gewoon herhalen tot en met 9, de vierkantswortel van 81.
9 % 9 = 0, wat betekent dat 81 geen priemgetal is.
dit is logisch omdat 9 x 9 factoren van 81 zijn, wat betekent dat het niet voldoet aan de definitie van een priemgetal — een getal dat alleen gelijk kan worden gedeeld door zichzelf en 1.

in JavaScript kunt u de vierkantswortel van een getal vinden met behulp van wiskunde.vierkant. We schrijven het zo:

Math.sqrt(num);

laten we het gebruiken in onze functie die controleert of een getal een priemgetal is:

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

Waarom zijn priemgetallen zo nuttig?In Contact, het sciencefictionboek van Carl Sagan, sturen aliens een lange reeks priemgetallen als bewijs dat hun boodschap afkomstig is van een intelligente levenskracht. We communiceren (nog) niet met buitenaardsen via priemgetallen maar gebruiken ze op verschillende manieren hier op Planeet Aarde.

cicaden verschijnen synchroon in exacte priemgetallencycli. De onregelmatige cycli betekent dat er geen roofdieren zijn geëvolueerd om van deze insecten te leven. Ook het feit dat ze allemaal op tijd uit de grond komen verhoogt de overlevingskans van een individu.

schermen gebruiken priemgetallen om de kleurintensiteit van pixels te definiëren. Ze worden ook gebruikt in de vervaardiging van gereedschap om zich te ontdoen van harmonieën. Twee tandwielen die een veelvoud delen, zullen dezelfde tanden steeds opnieuw aangaan, wat leidt tot een ongelijkmatig slijtpatroon. Tandwielen met een priemgetal tanden op hun tandwielen gaan langer mee.

priemgetallen zijn echter meestal in de moderne computerbeveiliging. Het is niet zo moeilijk om grote priemgetallen te vinden, maar het is erg moeilijk om grote getallen in priemgetallen te factor.

het is gemakkelijk om uit te vinden dat 27 3 x 3 x 3 is, maar het is veel moeilijker om te vinden dat 2,244,354 2 x 3 x 7 x 53,437 is. En 2,244,354 is niet eens zo ‘ n groot getal. Het vinden van de belangrijkste factoren is technisch een kwestie van tijd, maar omdat het zo lang zal duren zeggen we dat het niet kan worden gedaan.

moderne encryptie-algoritmen maken gebruik van het feit dat er nog geen computer is die een supergroot getal kan nemen en snel kan achterhalen welke priemgetallen ervoor zijn gebruikt.

u kunt online winkelen of een versleuteld bericht verzenden via een app op uw telefoon, maar ergens helpen priemgetallen u om uw geheimen veilig te houden.

hier zijn nog drie links naar andere” een algoritme per dag ” artikelen:

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.