tjek om et tal er et primtal

hov...

echo gmp_prob_prime("6") . "\n";

sådan.. :o)

gmp er ikke kompileret ind i din php? Lav en phpinfo(), du leder efter:

                gmp
    gmp support     enabled

øhh.. er ikke lige med ?

Er med på phpinfo()

Men der står intet om gmp...

Så har du ikke adgang til gmp, så må du lave din egen test ;)
Her er et eksempel:

<?php

    function is_prime( $n )
    {
        if ( $n < 1 )
        {
            return false;
        }
        if ( $n == 2 )
        {
            return true;
        }
        $maxtest = ceil( sqrt( $n ) );
        for ( $i = 3; $i < $maxtest; $i++ )
        {
            if ( $n % $i == 0 )
            {
                return false;
            }
        }
        return true;
    }

    function t( $n )
    {
        echo $n . " er " . ( is_prime( $n ) ? '' : 'ikke ' ) . "et primtal.<br>";
    }

    t( 29 );
    t( 42 );

?>

if ( $n < 1 )

bør nok rettes til:

if ( $n <= 1 )

Tak men...

Dit eksempel fortæller at 10 er et primtal !!

jeg testede lige igen fra 1 til 10.. Allle tallene beregnes som primtal ??

Det er jo kun 1 2 3 5 7

Eeerh 2 sek ;)

1 er ikke et primtal

ok :o)

Joo... 1 kan divideres med 1 og sig selv da..

ikke fordi jeg gider blande mig så meget, men idet for at tælle løkke 1 op hver gang kan man tælle den 2 op.. og så skifte

    if ( $n == 2 )
        {
            return true;
        }

ud med

  if ($n % 2 == 0 )
        {
            return ($n == 2);
        }

blueye97> indeed det kan det, men 1 er pr definition ikke et primtal...

Nåh ok... Jeg er ikke matematikgeni... :o))

I min løkke skal

        for ( $i = 3; $i < $maxtest; $i++ )

ændres til:

        for ( $i = 2; $i <= $maxtest; $i++ )

BOING !!!

Det virker efter hensigten. Tak og værsgo'

nejnej.. det giver heller ikke mening... hvad laver du med din maxtest?

så vidt jeg kan se går det da galt, hvis man smider 8 derind.. Det er ikke mindre end 1 og ej heller er det lig 2.. maxtest bliver sat til 4 og så har vi at 3 % 4 == 0 så vi retunerer true

bromer, Ikke forstået? Jeg finder bare ud af hvor mange jeg er nødt til at teste, for at teste et tal n, er det kun nødvendigt at checke tallene op til sqrt(n)...

bromer, $n % $i - hvis $n er 8 vil den teste 8 % 2 == 0 og fejle allerede der ;)

ahh.. okay.. det virker fordi du ændrede din løkke.. Det så jeg ikke.. af ren performence bør funktionen ændres til:

  function is_prime($n) {
      if ($n % 2 == 0) {
            return ($n == 2);
      }
        $maxtest = ceil( sqrt( $n ) );
        for ($i = 3; $i < $maxtest; $i += 2)
        {
            if ( $n % $i == 0 )
            {
                return false;
            }
        }
        return true;
    }

bromer, ja det kunne man optimere med :) Funktionen vil så se således ud:

    function is_prime( $n )
    {
        if ( $n < 1 )
        {
            return false;
        }
        if ( $n % 2 == 0 )
        {
            return true;
        }
        $maxtest = ceil( sqrt( $n ) );
        for ( $i = 3; $i < $maxtest; $i += 2 )
        {
            if ( $n % $i == 0 )
            {
                return false;
            }
        }
        return true;
    }

Det var faktisk den jeg burde have rettet først ;)

lol ja det var så også forkert kom jeg til at tænke på, den første test skal stadig være der:

    function is_prime( $n )
    {
        if ( $n < 1 )
        {
            return false;
        }
        if ( $n == 2 )
        {
            return true;
        }
        if ( $n % 2 == 0 )
        {
            return false;
        }
        $maxtest = ceil( sqrt( $n ) );
        for ( $i = 3; $i < $maxtest; $i += 2 )
        {
            if ( $n % $i == 0 )
            {
                return false;
            }
        }
        return true;
    }

jaja.. så er det jo samme forslag.. der er ingen forskel på

        if ( $n == 2 )
        {
            return true;
        }
        if ( $n % 2 == 0 )
        {
            return false;
        }

og

      if ($n % 2 == 0) {
            return ($n == 2);
      }

bromer, Det er mig der sover, det er da rigtigt ;)

blueeye - grunden til 1 ikke er et primtal er at for et tal kan være et primtal skal det have 2 divisorer, hverken færre eller flere, og da 1 kun har en divisor {1}, kan det ikke være et primtal.

Fra "Matematik 2AL - Algebra" af Anders Thorup fra Københavns Universitet:

"Et naturligt tal p kaldes som bekendt et primtal hvis p > 1 og p kun har trivielle divisoerer (dvs hvis de enste posivitive divisorer i p er 1 og p)".

det er helt rigtigt det suxor sagde, men det ville da ikke være rigtig Lørdag, hvis man ikke kunne citere en matematiker.