napi algoritmus: hogyan lehet ellenőrizni a prímszámot a JavaScript-ben

Marina Shemesh
Marina Shemesh

követés

május 28, 2020 * 7 perc olvasás

szinte garantált, hogy a kódolási oktatás során valamikor felkérést kap arra, hogy írjon valamilyen típusú függvényt, amely magában foglalja a prímszámokat. Ez egy népszerű gyakorlat a rendszerindító táborok kódolásában, sőt néha még az állásinterjúkon is felbukkan.

mik azok a prímszámok?

a prímszám egy 1-nél nagyobb természetes szám, amelynek egyetlen tényezője az 1 és maga a szám. Ez azt jelenti, hogy csak egyenlően osztható meg 1-vel és önmagával.

a természetes számok pozitív egész számok, például 1, 5, 201, 229999 stb. A 0 szám, a törtek, a tizedesjegyek és a negatív számok nem természetes számok.

az 5-ös szám prímszám, mert csak az 1-es és az 5-ös faktorai vannak. Nincs más mód az 5-ös szám létrehozására.

a 4-es szám nem prímszám, mert a 2 x 2 4-et is ad nekünk.

a 20-as szám nem prímszám, mert az 5 x 4 20-at, valamint 2 x 10-et is ad nekünk.

a prímszámok soha nem egyenletesek (kivéve a 2-et)

az egyik leggyorsabb módszer annak ellenőrzésére, hogy egy szám prímszám-e vagy sem, annak ellenőrzése, hogy páros szám-e. Ha egy számot el lehet osztani 2 — vel anélkül, hogy maradékot hagyna, akkor már nem felel meg a prímszám definíciójának-egy számnak, amelyet csak egyenlően lehet elosztani 1-vel és önmagával.

a JavaScriptben a modulo operátor (%) segítségével ellenőrizhetjük a páros számokat.

a modulo operátor a maradékot adja vissza, miután egy egész számot elosztunk egy másikkal.
például 12 % 5 értéke 2.
és 59 % 5 értéke 4.

ha egy egész számot elosztunk 2-vel, a maradék pedig 0, akkor tudjuk, hogy az egész szám páros szám.

például 10% 2 = 0
és 2200 % 2 = 0

a JavaScript – ben ez így fog kinézni:
szám % 2 === 0

Tehát kezdjük el létrehozni a JavaScript függvényünket annak ellenőrzésére, hogy egy szám prímszám – e vagy sem:

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

ne feledje, hogy a 2 prímszám

a fenti függvény azonban azt is kijelenti, hogy a 2 nem prímszám, ezért újra kell írnunk a függvényünket. Gondoskodhatunk más egész számokról is, amelyek nem egész számok, mint például a 0 és a negatív számok.

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

a ‘return’ kulcsszó jelzi a függvény kilépését, ha igaz állítással találkozik. Ha a szám 2, a funkció leáll a második sorban:

if (num === 2) return true;

itt található az ismert prímszámok nagy listája, amely segít a funkció ellenőrzésében.
nem minden egyenetlen szám prímszám

ez a funkció jól működik annak ellenőrzésére, hogy egy szám páros-e vagy sem, de nem működik olyan egyenetlen számokkal, mint a 9 és a 27, amelyek nem prímszámok.

ellenőriznünk kell, hogy a paraméter felosztható-e más tényezőkre (kivéve az 1-et, magát és a 2-t) maradék nélkül. A 9-es számot például el lehet osztani 3-mal is.

ezt egy for ciklus használatával tesszük, ahol minden iterációnál a paramétert elosztjuk egy másik hurok változóval. A hurok addig fut, amíg nincsenek maradványok, vagy nincs több elérhető hurokváltozó.

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

a funkció folyamatosan hurkolja és ellenőrzi a maradékokat. Minden iterációnál az argumentumot elosztjuk egy új ciklusváltozóval, a maradékot pedig ellenőrizzük. Ha a maradék 0, az azt jelenti, hogy az argumentum teljesen osztható egy másik számmal, amely nem maga, és nem prímszám.

Oldaljegyzet: Mi a különbség egy paraméter és egy argumentum között?
a paraméterek a függvénydefiníció részeként használt változók. Például a num in függvény isPrime (num) a paraméter.

az argumentumok azok az értékek, amelyeket a függvény meghívásakor továbbítanak. Például
az isPrime(9) 9-es száma az argumentum.

ha van maradék, akkor a függvény ismét iterálódik, amíg el nem éri a

 i < num

határértéket, amikor a végső iteráció elérte, és még maradt maradék, az argumentum prímszám, és a függvény leáll.
egy hurokváltozóval zárulunk, amely egy számmal kisebb, mint a paraméter, mert nem érdekelnek az argumentumnál nagyobb tényezők.

gyors bemutató

mutassuk be ezt az 5-ös prímszámmal.

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;}

első hurok:
1. i = 2 és 2 < 5, tehát folytatjuk a
2 hurkot. 5 % 2 maradékot ad, így nem lépünk ki a hurokból, hanem folytatjuk az i++

második hurokkal:
1. i = 3 és 3 < 5, tehát folytatjuk a
2 hurkot. 5% 3 maradékot ad, így nem lépünk ki a hurokból, hanem folytatjuk az i++

harmadik hurokkal:
1. i = 4 és 4 < 5, és elértük a hurok végét, mert az 5 nem <, mint 5
2. 5% 4 ad maradékot. Ez azt jelenti, hogy az 5-ös szám prímszám

négyzetgyök használata nagyobb prímszámokkal

a prímszámok gyorsan hatalmas számokká válnak. Ez azt jelenti, hogy a For ciklusunk számos alkalommal folyamatosan iterál az egyik hurok változóról a másikra.

lerövidíthetjük a folyamatot egy paraméter négyzetgyökének használatával. Az egész szám négyzetgyöke az a szám, amelyet önmagával megszoroztak egy termék létrehozásához.

a 81 négyzetgyöke 9, Mert 9 x 9 = 81.

ahelyett, hogy 2-től 80-ig iterálnánk, hogy ellenőrizzük, maradt-e maradék vagy sem, csak 9-ig, a 81 négyzetgyökéig iterálhatunk.
9% 9 = 0, ami azt jelenti, hogy a 81 nem prímszám.
ennek azért van értelme, mert a 9 x 9 A 81 faktora, ami azt jelenti, hogy nem felel meg a prímszám definíciójának — egy olyan számnak, amelyet önmagában csak egyenlően lehet felosztani az 1-vel.

a JavaScriptben a szám négyzetgyökét a matematika segítségével találhatja meg.négyzet. Így írjuk:

Math.sqrt(num);

használjuk azt a függvényünkben, amely ellenőrzi, hogy egy szám prímszám-e:

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

miért olyan hasznosak a prímszámok?

in Contact, Carl Sagan tudományos-fantasztikus könyve, az idegenek prímszámok hosszú sorát küldik annak bizonyítékaként, hogy üzenetük intelligens életerőből származik. Nem (még) kommunikálunk a földönkívüliekkel prímszámokon keresztül, hanem különféle módon használjuk őket itt a Föld bolygón.

a kabócák szinkronban jelennek meg pontos prímszám-ciklusokban. A szabálytalan ciklusok azt jelentik, hogy egyetlen ragadozó sem fejlődött ki, hogy ezekből a rovarokból éljen. Továbbá, az a tény, hogy mindegyik időben a Földből származik, növeli az egyén túlélési esélyét.

a képernyők prímszámokkal határozzák meg a pixelek színintenzitását. A szerszámgyártásban is használják őket, hogy megszabaduljanak a harmóniáktól. Két fogaskerék, amelyek többszörösen osztoznak, újra és újra összekapcsolják ugyanazokat a fogakat, ami egyenetlen kopási mintázatot eredményez. Azok a fogaskerekek, amelyeknek a fogaskerekein prímszám van, tovább tartanak.

prímszámok azonban leginkább a modern számítógépes biztonság. Nem olyan nehéz megtalálni a nagy prímszámokat, de nagyon nehéz a nagy számokat prímszámokká alakítani.

könnyű kitalálni, hogy a 27 Az 3 x 3 x 3, de sokkal nehezebb megtalálni, hogy a 2,244,354 az 2 x 3 x 7 x 53,437. És a 2 244 354 nem is olyan nagy szám. Az elsődleges tényezők megtalálása technikailag idő kérdése, de mivel ilyen sokáig tart, azt mondjuk, hogy nem lehet megtenni.

a Modern titkosítási algoritmusok azt a tényt használják, hogy még nincs olyan számítógép, amely szuper nagy számot tudna venni, és gyorsan kitalálná, hogy melyik prímszám került bele.

lehet, hogy online vásárol, vagy titkosított üzenetet küld egy alkalmazáson keresztül a telefonján, de valahol, valahogy a prímszámok segítenek a titkok biztonságban tartásában.

itt van még három link más” egy algoritmus egy nap ” cikkekhez:

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé.