[es] - :[Prosti Brojevi...]:

Divine
Miloš Šaković
IT Manager
Yugoslavia

Član broj: 883
Poruke: 108
*.pg-dialup.cg.yu

ICQ: 16044064
Sajt: www.divine.cg.yu

Profil

:[Prosti Brojevi...]:

^{24.04.2002. u 20:37 - pre 267 meseci}

Pozdrav drugari,

Nesto mi je palo na pamet da vrtim proste brojeve. Napravio sam funkciju koja provjerava da li je broj prost. Pokusao sam da izlistam sve brojeve koji su prosti u intervalu od jedinice do 50 000. Evo funkcija:

Code:

function prost_br($broj) {

    $do = intval($broj / 2) + 1;
    $od = 2;

    for ($delitelj = $od; $delitelj <= $do; ++$delitelj) {
        $rezultat = $broj / $delitelj;

        if (! is_int($rezultat) ) {
            $izlaz = $broj;
        } else {
            $izlaz = false;
            break;
        } /* if */

    } /* for */

    return($izlaz);
} /* function */

E, sad da dam i kod za "vrtesku":

Code:

echo('<pre>');

for ($i = 1; $i <= 50000; ++$i) {
    $test = prost_br($i);

    if ($test != false) {
        echo $test . "\n";
    } /* if */

} /* for */

echo('</pre>');

Problem je sledeci:
Na mom kompjuteru uspijevam da doguram do cifre nesto vece od 11113 za 30 sekundi koliko mi je max exec time. Smatram da je ovo sporo! Moze li neko od vas, ko bolje zna matematiku, da smisli brze resenje?

p.s. Prost broj je broj koji je deljiv samo sa sobom i sa jedinicom (1, 3, 5, 7, 11, 13...)! (neka se oni koji znaju ovo ne uvrijede

)

I see dead people...

Odgovor na temu

_owl_

Član broj: 318
Poruke: 1043
*.drenik.net

+3 Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:22 - pre 267 meseci}

Pa sto se tice optimizacije
$do=round(sqrt($broj)); -- tj ides do korena.
A mozes da predajes i interval u kome trazis proste brojeve dok ces rezultate cuvati u nekom fajlu (nece se skoro menjati prosti brojevi).

Owl

Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.190.EUnet.yu

+3 Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:27 - pre 267 meseci}

posto prost broj mora da bude oblika 6k+1 ili 6k-1 ako je prost broj veci od 3 onda napisi ovakav program:
nekoj promenjljivoj k daj vrednost 4 a recimo i=5
proveri da li je broj 2 ili 3 a ako nije onda gledaj da li je deljiv sa i pa u sledecem
koraku uradi ovo: k^=6 (u pascalu k:=k xor 6) sto ti je isto kao i k=6-k u ovom slucaju jer ce se k menjati izmedju 2 i 4 ali sa xor je brze
i uradi ovo i=i+k;

znaci kad proveris da li je deljiv sa i uradis jos i ovo {k^=6;i++=k} posle u drugom koraku ce i biti 7 pa 11 pa 13 pa 17 pa 19 pa 23 itd.... povecava se za 2 pa za 4 itd...
obavezno kad napises program prenesi iskustva! ali obavezno, bas me zanima kolika je usteda u vremenu.
i naravno jos ovo: kad proveravas da li je broj n prost proveravaj samo do korena iz n ali nemoj da pises u for petlji da je i<=sqrt(n) za uslov jer ce ti onda u svakom koraju racunari sqrt(n) vec na pocetku programa napisi recimo koren=sqrt(n) pa onda u for petlji stavi da radi dok je i<=koren.

kad sam bio u srednjoj skoli obozavao sam da mucim profesore iz informatike kad na ovakav nacin proveravam da li je broj prost koristeci k^=6. mnogi nisu shvatali :-)

puno uspeha

[Ovu poruku je menjao srki dana 24.04.2002 u 10:30 PM GMT]

Odgovor na temu

Ivand
Ivan Dimitrijević
...
yu/pa

Član broj: 17
Poruke: 2161
*.panet.co.yu

Sajt: www.webmanijak.com

+4 Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:30 - pre 267 meseci}

na kraju krajeva ako nece muhamed bregu , onda ce breg muhamedu
povecas exec time ;)

http://webmanijak.com
http://www.balkapps.com

Odgovor na temu

Divine
Miloš Šaković
IT Manager
Yugoslavia

Član broj: 883
Poruke: 108
*.pg-dialup.cg.yu

ICQ: 16044064
Sajt: www.divine.cg.yu

Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 23:51 - pre 267 meseci}

Pazite, neka neko pokusa da uradi neku drugu varijantu? Mozda matematika pomogne, meni je to slabija strana. Postovacu ovo na stranim forumima.

I see dead people...

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
212.124.183.*

Sajt: localhost

+5 Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 02:09 - pre 265 meseci}

Citat:

Divine:
Pazite, neka neko pokusa da uradi neku drugu varijantu? Mozda matematika pomogne, meni je to slabija strana. Postovacu ovo na stranim forumima.

ako ti ovo i dalje treba (dobro sam se setio posle 2 meseca ;) postoji MNOGO bolje resenje (citaj 100+ puta brze)

Code:

<?php
    $max=50000;
    for ($i=0; $i<=$max; $i++) $a[$i]=1;
    $a[0]=0;
    $a[1]=0;
    $k=2;
    while ($k<=$max) {
        for ($j=2; $k*$j<=$max; $j++) $a[$k*$j]=0;
        $k++;
        while (($k<$max) and ($a[$k]==0)) $k++;
    }
    echo "<pre>";
    for ($i=1; $i<=$max; $i++) if ($a[$i]) echo $i."\n";
    echo "</pre>";
?>

a postupak je sledeci... recmio da trazis sve proste brojeve do 30... lepo napises na papir sve brojeve do 30:

Code:

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

a onda precrtash (obrises) sve koji su deljivi sa 2 (osim dvojke ;)

Code:

2 3 _ 5 _ 7 _ 9 __ 11 __ 13 __ 15 __ 17 __ 19 __ 21 __ 23 __ 25 __ 27 __ 29 __

zatim precrtash sve koji su deljivi sa 3, osim trojke, pa sa 5, osim petice, itd, itd...

Code:

2 3 _ 5 _ 7 _ _ __ 11 __ 13 __ __ __ 17 __ 19 __ __ __ 23 __ 25 __ __ __ 29 __
2 3 _ 5 _ 7 _ _ __ 11 __ 13 __ __ __ 17 __ 19 __ __ __ 23 __ __ __ __ __ 29 __

i to je to... onda svi oni koji su ostali, su prosti...

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

01011011

Član broj: 561
Poruke: 2341
*.in.us.prserv.net

+2 Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 02:35 - pre 265 meseci}

Evo ovako sam ja to uradio pre jos.

Code:

<html>
<head>
<title> Brojevi deljivi sa 1 i sa Samim sobom</title>
</head>
<body bgcolor=#000000 TEXT=#ffffff link=#blue alink=#ffffff vlink=lightblue>
<font face="verdana" SIZE=2>
<?php
//Promeni ovo ukoliko zelis vise Brojeva $n <= 1000
for ($n = 1; $n <= 1000; $n++)
{
    if (($n == 1) || ($n == 2) || ($n == 3) || ($n == 5))
    {
        print ("$n<BR>\n");
    }
    else if (($n % 2 !=0) && ($n % 3 != 0) && ($n % 5 != 0 ))
    {
        print ("$n<BR>\n");
    }//        Zatvaram if
}//        Zatvaram FOR
?>
</body>
</html>

ALi ako stavis prevelik broj onda ti nakon 30 sekundi dadne TIME OUT.

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
212.124.183.*

Sajt: localhost

+5 Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 03:29 - pre 265 meseci}

pa nije valjda cilj da svi napisu svoje resenje, nego da se nadje najbolje. ono sto sam ja napisao (al sam skroman), je sigurno najbrzi algoritam (ne racunajuci sitnu optimizaciju).

ovo na mojoj slaboj makini (P1/200Mhz) nalazi sve proste do 50,000 za manje od 30 sec. (nalazi i preko 500,000 ali prodje 30 sec dok on ispise (posalje) sve te brojeve do browsera...)

i josh jedna napomena (bez uvrede)... tvoj prog. nije tacan! nije prost broj onaj koji nije deljiv sa 2, 3 i 5!!! (sta je sa 7, 11, 13...).. recimo broj 49 nije deljiv ni sa 2 ni sa 3 ni sa 5, ali jeste sa 7, pa nije prost!

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

01011011

Član broj: 561
Poruke: 2341
*.in.us.prserv.net

+2 Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 09:30 - pre 265 meseci}

PA Mozda sam ja malko zamenio nesto. :)

Posto zivim u americi, mislim da se prosti brojevi kazu "PRIME NUMBERS" ako ne onda nista, ovaj moj program cupa Prime Numbers, ja sam pomslio da su to brojevi koji su deljivi samo sa 1 i sa samim sobom. Ako nisam u pravu onda nista.

Odgovor na temu

RAZZLEDAZZLER
Tora Bora

Član broj: 27
Poruke: 543
*.beg.sezampro.yu

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 12:41 - pre 265 meseci}

Jeste, to su prime numbers
I Jesi ti u pravu shto se tiche toga da su deljivi samo sa jedinicom i samim sobom ... ali tvoj kod nije u redu

Code:
else if (($n % 2 !=0) && ($n % 3 != 0) && ($n % 5 != 0 ))

Kao shto je rekao zombie / DDG, ova linija koja sluzi da proveri da li je broj prost, nije dobro napisana... tako da ce ti se provuci npr broj 49, jer ti ne proveravash da li je broj deljiv sa 7, 11, 13 ....itd [opet kao shto je zombie / DDG rekao].

Odgovor na temu