Priem getallen zoeker

Door Han eev, 22 jaar geleden, 6.507x bekeken

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

 

Er zijn 33 reacties op 'Priem getallen zoeker'

PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Jelmer -
Jelmer -
22 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.


22 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
22 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
22 jaar geleden
 
0 +1 -0 -1
je kan ook gewoon is_int doen aangezien een integer een geheel getal is :)
EdwinG
EdwinG
22 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
22 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
22 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
22 jaar geleden
 
0 +1 -0 -1
@Han: aan mij gericht? of aan Edwin?
Legolas
Legolas
22 jaar geleden
 
0 +1 -0 -1
het is een priem getal ;)


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


22 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.
Jelmer -
Jelmer -
22 jaar geleden
 
0 +1 -0 -1
Google zegt ook priemgetal.
Jan Koehoorn
Jan Koehoorn
22 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
22 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
22 jaar geleden
 
0 +1 -0 -1
@ Edwin: da's ook toevallig! Zo werkt die functie die ik bewerkt heb :-)
EdwinG
EdwinG
22 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
22 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
22 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
22 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
22 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
Onbekend onbekend
onbekend onbekend
22 jaar geleden
 
0 +1 -0 -1
Maak je er ook een voor volmaakte getallen? en volmaakte paren?
Han eev
Han eev
22 jaar geleden
 
0 +1 -0 -1
En dat is...
Jan Koehoorn
Jan Koehoorn
22 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
22 jaar geleden
 
0 +1 -0 -1
Cool... Zal is even kijken.
Legolas
Legolas
22 jaar geleden
 
0 +1 -0 -1
voorbeeld klopt niet, 22 is geen priem getal bijvoorbeeld
Jan Koehoorn
Jan Koehoorn
22 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
22 jaar geleden
 
0 +1 -0 -1
@legolas: klopt zal ik verbeteren

Edit: Klaar
Han eev
Han eev
22 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
22 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
22 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
22 jaar geleden
 
0 +1 -0 -1
Alles kan beter ^^
Kasper
Kasper
22 jaar geleden
 
0 +1 -0 -1
Ja, idd
Eigenlijk is nog beter als je alleen deelt door eerder gevonden priemgetallen.
PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Martijn Wieringa
Martijn Wieringa
19 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.

Inhoudsopgave

  1. priem-getallen-zoeker

Labels

  • Geen tags toegevoegd.

Navigatie

 
 

Om de gebruiksvriendelijkheid van onze website en diensten te optimaliseren maken wij gebruik van cookies. Deze cookies gebruiken wij voor functionaliteiten, analytische gegevens en marketing doeleinden. U vindt meer informatie in onze privacy statement.