Versio

Priem getallen zoeker

Ik verveelde me weer eens...
En we hadden het bij wiskunde over priem getallen dus ik ging maar eens ff kijken
of je die met php kan opzoeken!
Ja dus...


Han

(Dit is gewoon grappig, niet nuttig!)

Edit: met de tips heb ik nu een script dat sneller is en minder loopt hoeft te maken

Voorbeeld: http://haneev.nl/voorbeeld/prim/prim.php

Gesponsorde koppelingen

PHP script bestanden

  1. priem-getallen-zoeker

 

33 reacties op 'Priem getallen zoeker'

PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Jelmer rrrr
Jelmer rrrr
8 jaar geleden
 
0 +1 -0 -1
Ik heb ook eens zo'n wiskundig script voor worteltrekken gemaakt, en dat is een prima oefening om te leren hoe je een computer moet aanpakken. Een computer heeft namelijk geen inzicht, maar wel veel rekenkracht. En ook jij maakt daar lekker gebruik van met je 100*100 loopje.


8 jaar geleden
 
0 +1 -0 -1
Leuk. Maar kan je niet beter:
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
<?php
if ($deel == ceil($deel))
{
  $arr[$i][$j] = $deel;
}
?>

doen i.p.v.
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
<?php
        $ex = explode('.',$deel);
        if(!isset($ex[1])) {
        $arr[$i][$j] = $deel;
?>

Zo hoeft er geen array aangemaakt te worden en is hij ook bruikbaar als PHP , gebruikt ipv .
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
Goed script Han, al zou het voor grote getallen of voor grote getalbereiken natuurlijk erg veel tijd gaan kosten. Er is niet één ideaal algoritme voor priemgetallen te vinden, maar deze zal voor kleine getallen prima voldoen.
Legolas
Legolas
8 jaar geleden
 
0 +1 -0 -1
je kan ook gewoon is_int doen aangezien een integer een geheel getal is :)
EdwinG
EdwinG
8 jaar geleden
 
0 +1 -0 -1
for($i = $begin;$i<$eind;$i++) {
for($j=$begin;$j<$eind;$j++) {

$j hoeft helemaal niet zo hoog te zijn, zodra deze hoger is dan $i weet je toch zeker dat er geen geheel getal meer uitkomt.

Iets minder rekenkracht nodig, (maar er kan alsnog een hoop verbeteren)
for($i = $begin;$i<$eind;$i++) {
for($j=1;$j<$i;$j++) {

Je moet met de deler ($j) altijd bij 1 starten, want als $begin 10 is, zal het script 12 als priem getal opgeven.
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
Een mogelijke verbetering:

Stel testgetal = x

Dan hoef je maar te tellen totdat je NET voorbij de helft van x bent, want getallen die groter zijn dan de helft van het testgetal leveren bij deling ALTIJD een float op.
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
@geen idee
Dan werkt het niet helemaal
want als je dat doet kan je het getal door andere prim getallen delen!
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@Han: aan mij gericht? of aan Edwin?
Legolas
Legolas
8 jaar geleden
 
0 +1 -0 -1
het is een priem getal ;)


8 jaar geleden
 
0 +1 -0 -1
Ja dat dacht ook. Maar blijkbaar dus niet


8 jaar geleden
 
0 +1 -0 -1
Ik heb ook geleerd dat het priem was. Maar de leraar maakte nog wel heel wat meer (taal)fouten dus kleine kans dat hij het goed had.
PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Jelmer rrrr
Jelmer rrrr
8 jaar geleden
 
0 +1 -0 -1
Google zegt ook priemgetal.
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
Ik ben hier toch ook maar even mee aan de slag gegaan. Via wat Googlen heb ik een functie in C++ gevonden, die ik geport heb naar PHP. Verder heb ik wat aanpassingen gedaan.

Voorbeeldpagina: zoek alle priemgetallen tussen twee getallen
EdwinG
EdwinG
8 jaar geleden
 
0 +1 -0 -1
priemgetal idd.

Als je het aantal berekeningen verder wilt terugdringen:
Eigenlijk hoef je alleen te kijken of een getal te delen is door de priem getallen die kleiner zijn dan de wortel van het getal. (of gelijk aan)

Als je x deelt door een geta GROTER dan zijn wortel, krijg je namelijk een resultaat KLEINER dan zijn wortel, en die heb je dus in omgekeerde vorm al gehad.
(Zoals 8/2 = 4 en 8/4 = 2)

En je hoeft alleen te kijken naar andere priem getallen. (je kunt wel controleren of iets door 8 deelbaar is, maar als het niet door 2 deelbaar is, weet je dat eigenlijk al, en als het wel door 2 deelbaar is, is het geen priemgetal.)

Verder kun je naar het volgende cijfer gaan zodra je een uitkomst hebt zonder decimalen.
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@ Edwin: da's ook toevallig! Zo werkt die functie die ik bewerkt heb :-)
EdwinG
EdwinG
8 jaar geleden
 
0 +1 -0 -1
@Jan Koehoor: Dit is mijn versie, ik heb ze niet nagerekend, maar gaat tot 100.000 in minder dan 30 seconden.
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
<?php
set_time_limit(100);
                                                                                                                            
$start = 6;
$eind = 100000;
$priemgetallen = array(2,3,5);
$x = 0;
$is_priem = true;
                                                                                                                            
for ( $i = $start;$i <= $eind;$i++ )
{
        $tot = ceil(sqrt($i));
        $y = $priemgetallen[$x];
        while ( $is_priem && ($y <= $tot) )
        {
                if ( $i % $y == 0 )
                {
                        $is_priem = false;
                };
                $x++;
                $y = $priemgetallen[$x];
        };
        if ($is_priem)
        {
                $priemgetallen[] = $i;
        };
        $x = 0;
        $is_priem = true;
};
                                                                                                                            
foreach ($priemgetallen as $priem)
{
        echo "$priem, ";
};
?>
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@Edwin: da's een goeie performance toch? Ik heb ook even een timer op mijn script gezet. Als ik van 6 - 100000 invul, komt ie op een dikke negen seconden uit.
EdwinG
EdwinG
8 jaar geleden
 
0 +1 -0 -1
Heb je die code van de timer?
(en wat voor processor heb je?) Houd je er rekening mee dat als je bij zes begint, je 2,3,5 handmatig moet invullen als priemgetallen.
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@Edwin:

de code van die timer staat in de source van mijn voorbeeldpagina
De functie heet get_microtime. Aanroepen zodra het werkelijke rekenwerk begint, en nog eens als dat afgelopen is. Het verschil afronden indien nodig en klaar.

Mijn pagina rekent de priemgetallen uit tussen twee gegeven waardes, dus als ik bij 6 begin zijn 2,3,5 niet relevant.
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
Woow, ik maak een halfe revolutie met dit script ;)
En volgens mij is het idd Priem (niet goed opgelet bij wiskunde)

Han
Bienze onbekend
Bienze onbekend
8 jaar geleden
 
0 +1 -0 -1
Maak je er ook een voor volmaakte getallen? en volmaakte paren?
PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
En dat is...
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
Volmaakte getallen zijn getallen die je kunt schrijven als de som van hun echte delers. Bijv: 6 = 1 + 2 + 3
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
Cool... Zal is even kijken.
Legolas
Legolas
8 jaar geleden
 
0 +1 -0 -1
voorbeeld klopt niet, 22 is geen priem getal bijvoorbeeld
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@Legolas: heb ik net even bij "mijn" script getest, en daar klopt het wèl
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
@legolas: klopt zal ik verbeteren

Edit: Klaar
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
@Jan Koehoorn
Jou timer klopt niet want je moet het onderaan de pagina zetten en niet na het bereken want ik moest nog wel even wachter voordat ik alle tekst had!
Jan Koehoorn
Jan Koehoorn
8 jaar geleden
 
0 +1 -0 -1
@ Han: ik wil alleen de functie timen die de priemgetallen uitrekent, dus die timer staat prima zo.
Kasper
Kasper
8 jaar geleden
 
0 +1 -0 -1
Dit is mijn script het gaat tot de 800000 in 30 seconde.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Priemgetallen</title>
</head>
<body>
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
set_time_limit(30);
$n=11;

print ("2<br />\n3<br />\n5<br />\n7<br />\n");
while(true)
{
    $t=6;
    while(true)
    {
        if($n%($t-1)==0)//deelt met 6n-1
            {break;}
        if($n%($t+1)==0)//deelt met  6n+1
            {break;}            
        if ($t>sqrt($n))
            {print "$n<br />\n";
            break;}
        $t+=6;
    }
    if (($n+1)%6==0)
    {$n+=2;}
    else
    {$n+=4;}
}
?>

</body>
</html>
Han eev
Han eev
8 jaar geleden
 
0 +1 -0 -1
Alles kan beter ^^
Kasper
Kasper
8 jaar geleden
 
0 +1 -0 -1
Ja, idd
Eigenlijk is nog beter als je alleen deelt door eerder gevonden priemgetallen.
Martijn Wieringa
Martijn Wieringa
4 jaar geleden
 
0 +1 -0 -1
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
<?php

    $aPriemGetallen = array(2);

    for($i = 2; $i < 10000; $i++)
    {
        $bPriem = true;

        for($p = 0; $p < sizeof($aPriemGetallen); $p++)
        {
            if(($i % $aPriemGetallen[$p]) == 0)
            {
                $bPriem = false;
                break;
            }
        }

        if($bPriem)
        {
            $aPriemGetallen[] = $i;
        }
    }

    echo 'Gevonden priem getallen:<br>' . implode(', ', $aPriemGetallen);

?>

Om te reageren heb je een account nodig en je moet ingelogd zijn.

  • Details
  • Han eev
    Door:
    Han eev
  • 8 jaar geleden
  • 1.311 x bekeken
  • Labels
  • Geen tags toegevoegd.