[PHP] Controleren of getal een priemgetal is

[Verwijderd]

Hallo, ik ben bezig voor een praktische opdracht wiskunde
en ik heb het onderwerp cryptografie gekozen.
Nu wil ik controleren of een getal een priemgetal is,
en ik kan dus wel bv.

code:

if ($getal%2 != 0) {bla bla}

doen, maar dit is natuurlijk een HEEL makkelijk 'omzeilbare' voorwaarde, want bv. 15 voldoet eraan en is toch geen priemgetal (duh)

Nu wilde ik dus vragen of er misschien een functie of algorithme is die dit controleert

[Verwijderd]

Er zijn hier meerdere posts over geweest meen ik: [search=priemgetal]

[Verwijderd]

PHP:

<?
for ($i = 1; $i < Math.sqrt($number); $i++) {
  if ($number / $i == Math.floor($number / $i)) echo "geen priem";
}
?>

De rest kun je zelf wel verzinnen.
Als je efficiënt wilt werken, hoef je alleen door bekende priemgetallen te delen...

Hint:
Zet alle bekende priemgetallen in een array priem[] en ga deze af met een loopje

[Rukapul]

Die oplossing is verschrikkelijk inefficient Cheatah

Het controleren of een getal een priemgetal is kan heel efficient bepaald worden en ook nog met een bepaalde foutmarge. Ik zal zo even Googlen naar het algoritme.

Het controleren of een getal een priemgetal is, is stukken makkelijker dan het vinden van nieuwe priemgetallen

[tomato]

Zoek naar De Zeef van Eratosthenes (of The Sieve of Eratosthenes), dat algoritme is gemakkelijk te gebruiken en te implementeren. Verder zou ik het niet zoeken als ik jou was.

Overigens, Cheatah, waar haal jij Math.sqrt() en Math.floor() vandaan?

[Verwijderd]

Op woensdag 05 december 2001 18:05 schreef tomato het volgende:

Overigens, Cheatah, waar haal jij Math.sqrt() en Math.floor() vandaan?

Mmmphf, goed dat je het zegt

/me is gek geworden van een overdosis DHTML

[Verwijderd]

Bedankt alvast allemaal,
ik heb de Zeef van Eratosthenes even bekeken, en dat ziet er goed uit, alleen volgens mij duurt die berekening wel ERG lang, aangezien de praktische opdracht (werkstuk) over cryptografie gaat, en daarin werk je met hele grote priemgetallen.

[Verwijderd]

Ik heb mijn PO voor Wiskunde B over priemgetallen gehouden.
Vooral aan http://www.utm.edu/research/primes/ en http://mathworld.wolfram.com/topics/PrimeNumbers.html had ik veel.
Als je m'n PO nog wilt bekijken moet je maar ff mailen...

[Rukapul]

De zeef nogwattes doet niet wat de topicstarter vraagt. Hij wil alleen maar testen of een getal een priemgetal is (handig bij het genereren van priemgetallen).

Op pagina 259 van Applied Cryptography 2nd ed. staan een aantal van dergelijke testen:
- Solovay-Strassen
-Lehmann
-Rabin-Millen (The algorithm everyon uses - it's easy- )

[tomato]

Rukapul:De zeef nogwattes doet niet wat de topicstarter vraagt.

Je hebt gelijk, ik had de vraag niet goed gelezen

Hij wil alleen maar testen of een getal een priemgetal is (handig bij het genereren van priemgetallen).

Mwah, handig, je genereert er letterlijk priemgetallen mee.

Dondervogeltje: alleen volgens mij duurt die berekening wel ERG lang, aangezien de praktische opdracht (werkstuk) over cryptografie gaat, en daarin werk je met hele grote priemgetallen.

Dat is nou juist de grap van die grote getallen die gebruikt worden. Die ontbind je niet zomaar even