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

Divine
Miloš Šaković
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}

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...

^{24.04.2002. u 20:37}

_owl_
Centar - BG

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

Sajt: home.drenik.net/~owl

Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:22}

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

^{24.04.2002. u 22:22}

srki
Srdjan Mitrovic
Auckland, N.Z.

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

Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:27}

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]

^{24.04.2002. u 22:27}

Ivand
Ivan Dimitrijević
yu/pa

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

Jabber: artur_dent@elitesecurity.org
Sajt: www.fotomanijak.com

Profil

Re: :[Prosti Brojevi...]:

^{24.04.2002. u 22:30}

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

http://fotomanijak.com kad porastem bicu dpreview ;)

^{24.04.2002. u 22:30}

Divine
Miloš Šaković
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}

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...

^{24.04.2002. u 23:51}

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

Član broj: 4128
Poruke: 3448
212.124.183.*

Sajt: localhost

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 02:09}

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}}

^{23.06.2002. u 02:09}

01011011
Nikola Ivetić
CHICAGO, USA

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

ICQ: 45747235
Sajt: www.memorizeme.net

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 02:35}

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.

Za druge se navija, Partizan se VOLI.
http://www.tipliga.com | http://www.pljuga.com | http://www.inno-studio.com | http://www.memorizeme.net

^{23.06.2002. u 02:35}

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

Član broj: 4128
Poruke: 3448
212.124.183.*

Sajt: localhost

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 03:29}

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}}

^{23.06.2002. u 03:29}

01011011
Nikola Ivetić
CHICAGO, USA

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

ICQ: 45747235
Sajt: www.memorizeme.net

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 09:30}

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.

Za druge se navija, Partizan se VOLI.
http://www.tipliga.com | http://www.pljuga.com | http://www.inno-studio.com | http://www.memorizeme.net

^{23.06.2002. u 09:30}

RAZZLEDAZZLER
Tora Bora

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

Profil

Re: :[Prosti Brojevi...]:

^{23.06.2002. u 12:41}

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].

^{23.06.2002. u 12:41}