Avatar billede mikl-dk Nybegynder
11. juni 2002 - 14:40 Der er 41 kommentarer og
3 løsninger

Primtal

Jeg er ved at lave noget kode, så man kan finde primtal indenfor en angivet interval. Men det virker ikke (har siddet og kigget på det, men kan ikke se en ladeport, selvom jeg står lige udenfor den...).

Hvis nogle har nogle forslag, er de også velkomne...

Kode:

$prim_tal_start        = 0;
$max_tal             = 40;

$fejl                = 0;

    for ($prim_tal_start; $prim_tal_start > $max_tal; $prim_tal_start++)
    {
       
            $min_div    = 2;
            $max_div    = $prim_tal_start;
       
            for ($min_div; $min_div > $max_div; $min_div++)
            {
                if (($prim_tal_start / $min_div) != ($prim_tal_start % $min_div))
                    {
                    $fejl = 1;
                    }
            }
   
       
        if ($fejl == 0)
        {
        echo "$prim_tal_start er et primtal";
        echo "<BR>";
        }
       
    }
Avatar billede panic-killer Nybegynder
11. juni 2002 - 14:46 #1
hvad er primtal og hvad kan man bruge dem til
Avatar billede panic-killer Nybegynder
11. juni 2002 - 14:47 #2
er n00b til php men:

$prim_tal_start        = 0;
$max_tal            = 40;

$fejl                = 0;      her giver du "fejl" 0 som verdi

    for ($prim_tal_start; $prim_tal_start > $max_tal; $prim_tal_start++)
    {
       
            $min_div    = 2;
            $max_div    = $prim_tal_start;
       
            for ($min_div; $min_div > $max_div; $min_div++)
            {
                if (($prim_tal_start / $min_div) != ($prim_tal_start % $min_div))
                    {
                    $fejl = 1;      her giver du "fejl" 1 til verdi
                    }
            }
   
       
        if ($fejl == 0)
        {
        echo "$prim_tal_start er et primtal";
        echo "<BR>";
        }
       
    }
Avatar billede panic-killer Nybegynder
11. juni 2002 - 14:48 #3
ved ikke om det er rigtigt men...
Avatar billede gizmo-gizmo Nybegynder
11. juni 2002 - 14:56 #4
panic-killer >> et primtal er et tal som kun 1 og tallet selv går op i. Fx: 2, 3, 7, 9, 13, 17, 19
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:01 #5
Primtal er tal, der kun kan divideres med tallet selv og 1, for at det giver et helt tal...

Beskrivelse af script:

$prim_tal_start        = 0; // intervalstrar
$max_tal            = 40; // intervalstop


$fejl                = 0; // sætter, at der ikke er fejl

    for ($prim_tal_start; $prim_tal_start > $max_tal; $prim_tal_start++)
    {
/* for-lykke, der kører alle hele tal i den oplyste interval igennem, og checker om dem med sciptet i denne løkke */
       
            $min_div    = 2; // starttallet
            $max_div    = $prim_tal_start;

/* overstående er "divisions-intervallet", altså de tal, jeg prøver at dividere med */

            for ($min_div; $min_div > $max_div; $min_div++)
            {
                if (($prim_tal_start / $min_div) != ($prim_tal_start % $min_div))
// hvis tallet divideret med divisionstallet er anderledes end heltalsdivision med divisiontallet er det et primtal
                    {
                    $fejl = 1;
                    }
            }
   
       
        if ($fejl == 0)
        {
        echo "$prim_tal_start er et primtal";
        echo "<BR>";
        }
       
    }

Der er fejl i scriptet, så derfor skal du ikke hænge dig så meget i det....
Avatar billede gizmo-gizmo Nybegynder
11. juni 2002 - 15:05 #6
hmm... hvis man nu vil have fx et interval fra:
3815615 til 98754677664


... får man så ikke et hastigheds problem???? :)
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:07 #7
Jo, det er jeg sikker på, at man gør :)

Det er ikke pga., at jeg vil forske i KÆMPE primtal, men for at kode for sjov. Da jeg godt kan lide matematik, kan jeg godt lide sådanne små koder...
Avatar billede o-zone Nybegynder
11. juni 2002 - 15:12 #8
Den hurtigste måde at finde primtal på er at have den fulde mængde tal, og så løbe alle tabellerne fra 2 og op ad gennem, og strippe de tal der kommer frem! :-(

Det er ikke specielt hurtigt, hvis vi taler om meget store primtal, men havde det været let, så ville man jo ikke kunne have brugt dem i krypto-business ;-)
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:14 #9
Det er jo ikke alle primtal man får frem ved at finde alle ulige tal - 15 er jo ikke et primtal, da 5 * 3 = 15....
Avatar billede o-zone Nybegynder
11. juni 2002 - 15:18 #10
Den metode jeg forklarede om før er opfundet af den gamle græker Eratosthenes (og den virker selvfølgelig kun smart, så længe der er tale om relativt små tal).
Du kan læse meget mere om primtal på f.eks.:
http://www.utm.edu/research/primes/

:-)
Avatar billede tipsen Nybegynder
11. juni 2002 - 15:19 #11
gizmo: 9 et primtal... :-/
Avatar billede jakoba Nybegynder
11. juni 2002 - 15:21 #12
Avatar billede o-zone Nybegynder
11. juni 2002 - 15:22 #13
tipsen>> Nej det er ikke 3 * 3 = 9 !!! :-(
Avatar billede gizmo-gizmo Nybegynder
11. juni 2002 - 15:22 #14
tipsen >> skulle der ikke have stået: "9 ER et primtal" ?? ... Ja, okay, det gik lige hurtigt... 3*3 of course
Avatar billede o-zone Nybegynder
11. juni 2002 - 15:22 #15
tipsen>>> oops... så ikke helt hvad du skrev :")
Avatar billede gizmo-gizmo Nybegynder
11. juni 2002 - 15:23 #16
o-zone >> det var en stavefejl, tror ikke du skal satse på, at tipsen ikke ved det. Ellers er jeg i hvert fald skuffet :))
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:23 #17
Nu tror jeg dælme, at det virker:

$prim_tal_start        = 0;
$max_tal             = 100;

    for ($prim_tal_start; $prim_tal_start < $max_tal; $prim_tal_start ++)
    {
       
        $heltalsdivision    = round(($prim_tal_start / 2));
        $almindeligdivision    = ($prim_tal_start / 2);

        if ($heltalsdivision == $almindeligdivision)
        {
            $fejl = 1;
        }
   
        else
        {
            $min_div    = 2;
            $max_div    = $prim_tal_start - 1;
       
            for ($min_div; $min_div < $max_div; $min_div ++)
            {

                $heltalsdivision    = round(($prim_tal_start / $min_div));
                $almindeligdivision    = ($prim_tal_start / $min_div);

                if ($heltalsdivision == $almindeligdivision)
                    {
                    $fejl = 1;
                    }
            }
        }
       
        if (!$fejl)
        {
        echo "$prim_tal_start er et primtal";
        echo "<BR>";
        }

        $fejl    = NULL;
    }
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:24 #18
Satser ikke på det - I er jo alle sammen eksperter :)

Prøv lige at kør det igennem (hvis i gider), og sig, hvis I kan finde nogle tal, der ikke burde være der....
Avatar billede gizmo-gizmo Nybegynder
11. juni 2002 - 15:27 #19
nej det ser meget fair ud.
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 15:35 #20
Tak for kommentarerne...

Jeg har lavet lidt småjusteringer - her er det "prototype-scriptet":

$prim_tal_start        = 0;
$max_tal             = 100;

$antal_primes         = 0;

    for ($prim_tal_start; $prim_tal_start < $max_tal; $prim_tal_start ++)
    {
       
        $heltalsdivision    = round(($prim_tal_start / 2));
        $almindeligdivision    = ($prim_tal_start / 2);

        if ($heltalsdivision == $almindeligdivision)
        {
            $fejl = 1;
        }
   
        else
        {
            $min_div    = 2;
            $max_div    = $prim_tal_start - 1;
       
            for ($min_div; $min_div < $max_div; $min_div ++)
            {

                $heltalsdivision    = round(($prim_tal_start / $min_div));
                $almindeligdivision    = ($prim_tal_start / $min_div);

                if ($heltalsdivision == $almindeligdivision)
                    {
                    $fejl = 1;
                    }
            }
        }
       
        if (!$fejl)
        {
        echo "$prim_tal_start er et primtal";
        echo "<BR>";
        $antal_primes ++;
        }

        $fejl    = NULL;
    }

echo "<br><br>Der blev fundet: $antal_primes primtal...";
Avatar billede jakoba Nybegynder
11. juni 2002 - 16:03 #21
$mangetal = array( 10000 );

for ( $i=0; $i<10000; $i++ ) {  // initier talarray
    $mangetal[$i] = 1;
}

for ( ptal=2; $ptal<100; $ptal++ ) { // §1 lav sien
    if ( $mangetal[$ptal] ) {
        for ( $sital = 2*$ptal; $sital<10000; $sital+=$ptal ) {
            $mangetal[$sital] = 0;
        }
    }
}

for ( $i=2; $i<10000; $i++ ) {  // se hvad der kom ud af det
  if ( $mangetal[$i] ) {
      echo  $i.", ";
  }
}

// hvorfor er det ok at stoppe ved 100 i forløkken mærket med §1?

mvh JakobA
Avatar billede o-zone Nybegynder
11. juni 2002 - 16:07 #22
jacoba>> ahhh - Eratosthenes :o<
Jeg sidder selv og fedter med den, men der havde sneget sig en lille dum fejl ind!
Fair nok - jeg var ikke så hurtig som dig ;-)
Avatar billede o-zone Nybegynder
11. juni 2002 - 16:10 #23
Jacoba>> erh ... hvor har du den kode fra ... nej! Det er absolut ikke ok at stoppe ved 100! :-/
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:10 #24
JakobA <- Jeg synes, at min er lettere at forstå... Har du selv lavet den?
Avatar billede o-zone Nybegynder
11. juni 2002 - 16:13 #25
Mikl-dl>> Det er meget muligt at din kode er mere intuitiv (ved første øjekast), men hvor hurtig er den?
Har du prøvet at køre den igennem for f.eks. 1 - 10000?

Når du finder primtal, bliver hastigheden pænt hurtigt en altafgørende faktor! :)
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:18 #26
Ja, det har du ret i, at det er en altafgørende faktor!

Men såvidt jeg kan se, så er min også hurtig (den sorterer jo allerede halvdelen fra i starten - alle de lige tal)...

Det er også nemt at skifte max-grænsen i min (det kan også laves i den anden).

Jeg tror egentlig, at min er hurtig nok...

Kom til at tænke på, er der ikke en kommando, der gør, at man stopper den igangværende for-løkke (ikke exit, den stopper det hele)??
Avatar billede jakoba Nybegynder
11. juni 2002 - 16:25 #27
o-zone >> så find du et ikke-primtal til mig iblandt dem der skrives ud :-))
Avatar billede jakoba Nybegynder
11. juni 2002 - 16:27 #28
I en forløkke kan du sige  break;  for at 'hoppe ud' af løkken
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:30 #29
JakobA -> Tak - kanon hastighedsoptimering! Nu kan jeg få min til at stoppe MEGET hurtigere!!!!
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:42 #30
Har lige prøvet at teste med og uden....
Med break: 6329 primtal
Uden break: 3137 primtal

Det er de antal den er nået inden en time-out....

Så man må sige, at der er STOR forskel...
Avatar billede jakoba Nybegynder
11. juni 2002 - 16:47 #31
Det var ligegodt også et godt stykke vej. Er dit $max-tal ikke oppe på flere millioner.
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:50 #32
Nej satte det til 8000 - men lige nu sidder jeg og arbejder på min bærbare og laver en masse ting, så min php-server (kører den localhost ligenu) kan ikke regne hel vildt meget ud...
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 16:53 #33
Nu er der ved at gå sport i det :)

Jeg tror, at jeg vil prøve at lave det om til C++ og køre det på en af mine venners P4 2 GHz 512 MB RAM en nat, og se hvor mange den kan finde...
Avatar billede jakoba Nybegynder
11. juni 2002 - 16:58 #34
husk at sikre dig at din c-compiler laver 32-bil integer. eller brug evt long's :-))
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 17:06 #35
Jep - ellers kan tallene ikke være store nok...
Bruger Borland C++ Builder 5 - Enterprise Edition
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 17:11 #36
Hvad vil det hurtigste være / hvad kan computeren regne mest ud med:
1) Et GUI-interface?
2) En "kommando" promt
Avatar billede jakoba Nybegynder
11. juni 2002 - 17:20 #37
Det kommer an på hvormeget du bruger interfacet undervejs. netop dette program kan jo sidde og gnave i lang tid før der skal skrives noget ud, så det er ret ligemeget.

generelt vil jeg tro kommandopromptet er en smule hurtigere. det allerhurtigste er nok at skrive output til en fil.
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 17:33 #38
Ja, det regner jeg også med. Lave en kommandopromt, der skriver alle primtallene til en fil, og hvor mange primtal der er i alt...
Avatar billede jakoba Nybegynder
11. juni 2002 - 18:07 #39
en lille optimering:

                $heltalsdivision    = round(($prim_tal_start / $min_div));
                $almindeligdivision    = ($prim_tal_start / $min_div);
                if ($heltalsdivision == $almindeligdivision)

kan skrives som:

                $almindeligdivision    = ($prim_tal_start / $min_div);
                if ($almindeligdivision == round($almindeligdivision) )

så sparer du en division og en assigment hver gang igennem den indre løkke.
Avatar billede mikl-dk Nybegynder
11. juni 2002 - 23:35 #40
Jep - det har du ret i... Danke...
Avatar billede tipsen Nybegynder
11. juni 2002 - 23:54 #41
Har da også lige et bidrag til diskussionen:

(Genererede 6057 primtal på 27.562020897865 sekunder på min 1200mhz)

$primtalarray = array(2);
for ($i=3;$i<60000;$i+=2) {
  $sqrti = sqrt($i);
  foreach ($primtalarray as $primtal) {
    if (!($i % $primtal)) break;
    if ($primtal > $sqrti) {
      $primtalarray[] = $i;
      break;
    }
  }
}

//Udskriv de fundne primtal
foreach ($primtalarray as $primtal) {
  echo "$primtal<br>";
}


//Samme udgave - bare med tidtagning:

function getmicrotime(){
    list($usec, $sec) = explode(" ",microtime());
    return ((float)$usec + (float)$sec);
}

$time_start = getmicrotime();

$primtalarray = array(2);
for ($i=3;$i<60000;$i+=2) {
  $sqrti = sqrt($i);
  foreach ($primtalarray as $primtal) {
    if (!($i % $primtal)) break;
    if ($primtal > $sqrti) {
      $primtalarray[] = $i;
      break;
    }
  }
}

$time_end = getmicrotime();

$time = $time_end - $time_start;

echo "Genererede ".count($primtalarray)." primtal på $time sekunder!";

foreach ($primtalarray as $primtal) {
  echo "$primtal<br>";
}
Avatar billede mikl-dk Nybegynder
12. juni 2002 - 00:06 #42
tipsen <- jeg kan godt se, at dit ikke fylder så meget....
Men jeg kan ikke finde rundt i det, så godt som jeg kan i mit eget - men det er selvfølgelig også nemmere, når man selv har lavet det (har også kun programmeret php i under 1 år, men det skal nok komme :)

Gider du prøve køre mit igennem - så man kan sammenligne testresultater....

Kode (nu har jeg koblet nogle flere ting på, men alligevel):

function PrimeFind($max_tal=100, $order = 'vandret', $tekst = 0, $tekst_describe = 'er et primtal')
{





$prim_tal_start        = 0;

$max_tal++;

$antal_primes         = 0;



    for ($prim_tal_start; $prim_tal_start < $max_tal; $prim_tal_start ++)
    {
       
        $almindeligdivision    = ($prim_tal_start / 2);

        if (round($almindeligdivision) == $almindeligdivision)
        {
            $fejl = 1;
        }
   
        else
        {
            $min_div    = 2;
            $max_div    = $prim_tal_start - 1;
       
            for ($min_div; $min_div < $max_div; $min_div ++)
            {

                    $almindeligdivision    = ($prim_tal_start / $min_div);

                    if (round($almindeligdivision) == $almindeligdivision)
                    {
                    $fejl = 1;
                    break;
                    }
            }
        }
       
        if (!$fejl)
        {

            if ($tekst == 0)
            {
                if($order == "vandret")
                    echo "$prim_tal_start, ";

                if($order == "lodret")
                    echo "$prim_tal_start<BR>";
            }


            if ($tekst == 1)
            {
                if($order == "vandret")
                    echo "$prim_tal_start $tekst_describe, ";

                if($order == "lodret")
                    echo "$prim_tal_start $tekst_describe<BR>";
            }



        $antal_primes ++;
        }

        $fejl    = NULL;
    }

echo "<br><br>Der blev fundet: <b>$antal_primes</b> primtal...";
}
Avatar billede tipsen Nybegynder
12. juni 2002 - 00:13 #43
mikl:Du kan bare prøve at køre min stump - du kan eks. bare copy/paste den anden udgave jeg har copy/pastet - den med tidsforbrug!
Avatar billede mikl-dk Nybegynder
12. juni 2002 - 00:28 #44
Dooh - min hjerne er åbenbart slukket!! Selvfølgelig kan jeg bare køre den på min.....

Tak for det - det prøver jeg i morgen - vi i seng...
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Vi tilbyder markedets bedste kurser inden for webudvikling

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester