Scripts - Tutorials - Forum - Downloads - Showcase - Contact

Artikels

VPN vergelijken

Algemeen

Beginpagina

FAQ

Grafische worm (243)

Links

Nieuwsartikels

Nieuwsarchief

Boeken programmeren

Overzicht

Samenwerken

Webhosting

Zoek op Sitemasters

Leden

Registreren

Ledenlijst

Ons team

Links

webhostingtop10.be

Sociale media

Follow @sitemasters

Sitemasters

Adverteren op Sitemasters?

Contacteer ons

RSS

Link naar ons

Donaties

Poll

Je moet ingelogd zijn om te stemmen.

Statistieken

Linkpartners

Scripts:

Scripts > PHP > Wiskunde > Priemgetallen zoeken (eratosthenes zeef)

Priemgetallen zoeken (eratosthenes zeef)

Auteur: Thomas - 27 augustus 2004 - 14:48 - Gekeurd door: Dennisvb - Hits: 10412 - Aantal punten: 4.19 (8 stemmen)

Met behulp van eratosthenes zeef worden alle priemgetallen uit een interval [2..n] 'gezeefd'. Dit werkt als volgt:

Gegeven een getal n (>1), de lijst L [2, ..., n], de lege lijst P
doe, zolang L niet leeg is
g is het kleinste getal in de lijst L
voeg dit getal toe aan P
verwijder alle veelvouden van g uit L
einde doe

Na afloop is dus L leeg, en bevat P alle priemgetallen uit het interval [2..n]

Bij onderstaande implementatie is gebruik gemaakt van het feit dat elk getal is opgebouwd uit priemgetallen.

Mogelijke optimalisatie:
Je zou alleen priemgetallen hoeven te controleren die kleiner zijn dan of
gelijk zijn aan de wortel van het te controleren getal, immers als je geen
getal a hebt zodat
g = a*b en a <= wortel(g)
dan is er ook geen getal b zodat
g = a*b en b >= wortel(g)

Mogelijke uitbreiding:
Als je wat grotere priemgetallen wilt gaan berekenen zal je een mechanisme
moeten bedenken waarbij eerder berekende priemgetallen worden opgeslagen, en
weer worden opgehaald op het moment dat je wilt bepalen of een bepaald getal
een priemgetal is.

Code:

eratosthenes zeef:

php code - Bekijk de code zonder highlighting - Klap code in

<?php
function erathostenes($end) {
  // maakt gebruik van het feit dat elk getal opgebouwd is uit priemgetallen

  // pre: $end is een positief geheel getal (>0)
  // ret: een array met alle priemgetallen tussen [2..$end]

  $primes = array(); // array van priemgetallen (wordt geretourneerd)
  $current = 2; // start nummer voor het zoeken naar priemgetallen (niet veranderen)

  while($current <= $end) {
    // is het huidige getal een veelvoud van een priemgetal ?
    $i = 0;
    while($i < sizeof($primes) && ($current % $primes[$i]) > 0) {
      $i++;
    }
    if($i == sizeof($primes)) {
      // het huidige getal is een priemgetal
      $primes[] = $current;
    }
    $current++;
  }
  // retourneer het resultaat
  return $primes;
}
?>

<?php
function erathostenes($end) {
  // maakt gebruik van het feit dat elk getal opgebouwd is uit priemgetallen
 
  // pre: $end is een positief geheel getal (>0)
  // ret: een array met alle priemgetallen tussen [2..$end]
 
  $primes = array(); // array van priemgetallen (wordt geretourneerd)
  $current = 2; // start nummer voor het zoeken naar priemgetallen (niet veranderen)
 
  while($current <= $end) {
    // is het huidige getal een veelvoud van een priemgetal ?
    $i = 0;
    while($i < sizeof($primes) && ($current % $primes[$i]) > 0) {
      $i++;
    }
    if($i == sizeof($primes)) {
      // het huidige getal is een priemgetal
      $primes[] = $current;
    }
    $current++;
  }
  // retourneer het resultaat
  return $primes;
}
?>

tabel voor het afdrukken:

php code - Bekijk de code zonder highlighting - Klap code in

<?php
$getal = ...; // zelf in te vullen
$results = erathostenes($getal);

$cols = 20;
$rows = ceil($getal/$cols);
?>
<table border="1">
<?php
for($j=0; $j<$rows;$j++) {
?><tr><?php
  for($i=0; $i<$cols;$i++) {
    $nr = $cols*$j+$i+1;
?><td><?= ($nr <= $getal ? (in_array($nr, $results) ? "<b>".$nr."</b>" : $nr) : "<br />") ?></td><?php
  }
?></tr><?php
}
?>
</table>

<?php
$getal = ...; // zelf in te vullen
$results = erathostenes($getal);
 
$cols = 20;
$rows = ceil($getal/$cols);
?>
<table border="1">
<?php
for($j=0; $j<$rows;$j++) {
?><tr><?php
  for($i=0; $i<$cols;$i++) {
    $nr = $cols*$j+$i+1;
?><td><?= ($nr <= $getal ? (in_array($nr, $results) ? "<b>".$nr."</b>" : $nr) : "<br />") ?></td><?php
  }
?></tr><?php
}
?>
</table>

Download code (.txt)

Stemmen

Niet ingelogd.

Reacties

Post een reactie

Lees de reacties (2)