banjalukaforum.com

Ovo je stvar koju bas slabo znam. Trebami brz alogoritam za pronalazenje prosti brojeva. Znam 2, 3 ovakva alogoritma ali su mi prespori.

_________________
U raju je lijepo, ali u paklu je raja.

E ovako:
Posti brojevi su svi oni koji su djeljivi samo sa 1 i samim sobom.
Znaci prvo stavis da su jedan i dva prosti, a onda provjeravas samo neparne (jer su svi parni djeljivi bar jos sa 2) i provjeravas ih pomocu for petlje. Jos nesto nemoras provjeravati sve brojeve iz intervala 3-proizvoljan broj vec zbog nekog fazona koji sam zaboravio provjeravas samo od 3-sqrt(proizvoljan broj) sto znacajno ubrzava algoritam jer za recimo 1000000 brojeva ti provjeravas samo 1000. To bi trebalo biti tako. Nisam sad u stanju da ti pisem implementaciju u C-u jer sam cijelo jutro na predavanjima . A ako nadjes neki algoritam koji radi brze od ovoga postuj da vidim.
P.S. ovo radi samo za unsigned integer.

_________________

Linux registrated user No:396713 http://counter.li.org

Ovo je najbrzi algoritam za koji ja znam.

#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
long br=0,k,n,i,p;
printf("Unesi prirodan broj i bice ispisani svi prosti brojevi manji od njega: ");
scanf("%ld",&k);
for(n=1;n<k;n++)
{
p=1;
if(!(n%2)&&n!=2) p=0;
else
{
for(i=3;i<=sqrt(n);i+=2)
if(!(n%i))
{
p=0;
break;
}
}
if(p)
{
printf("%ld\t",n);
br++;
}
}
printf("\nUkupno ih ima %ld",br);
getch();
}

Sto se tice brzine ispise sve proste do 1 000 000 za 10 sekundi,ima ih 78 499.

PS
Moze se malo pojednostavni ako se 1 i 2 rucno ispisu,al se ne ubrza program.

#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
long br=2,k,n,i,p;
printf("Unesi prirodan broj i bice ispisani svi prosti brojevi manji od njega: ");
scanf("%ld",&k);
printf("1\t2\t",n);
for(n=3;n<k;n+=2)
{
p=1;
for(i=3;i<=sqrt(n);i+=2)
if(!(n%i))
{
p=0;
break;
}
if(p)
{
printf("%ld\t",n);
br++;
}
}
printf("\nUkupno ih ima %ld",br);
getch();
}

Moj(zaboravi sam kako se zove) alogoritam radi do 10.000.000 za oko sekund. trebao sam do 100.000.000. Jednostavno toliko ih mnogo ne moze pronaci brzo. Najbrzi sta ja znam. Napravimo niz od 2 do X tipa boolean. i postavimo sve vrednosti na true. znaci imamo niz:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

idemo od pocetka ka kraju niza na svaki broj na koji naidjemo ispisujemo. prvo nailazimo na dva i on je prost. zovemo funkciju i prosledjujemo joj broj na koji smo naisli. Ona taj broj mnozi od 2 do +besknacno sve dok prozvod nedadne broj veci od x. Svaki broj koji dobijemo mnozenjem krizamo.

Znaci ide ovako

_________________
U raju je lijepo, ali u paklu je raja.

Za ovaj algoritam nisam znao al ako je takav bas je brz.
Ne vidim sta ce ti brzi ako uopste postoji brzi od ovog.
Skontao sam ga djelimicno al ne znam kako bi ga realizovao u C-u.
Ajd postavi source code ako imas da vidim kako radi.
Pozdrav.

Evo alogoritma u pascalu; Izlaz ide u datoteku jer bi ispis potrajao dugo. Na mom racunaru za 10.000.000 radi 1.2 sec.

_________________
U raju je lijepo, ali u paklu je raja.

Divim se tvom neznanju. Taj algoritam se zove Eratostenovo sito. Drugi predlozeni algoritam (borisdj) je jako spor posto se sqrt(i) izracunava svaki put. Ako bi se ta vrijednost izracunala prije pozivanja unutrasnje petlje, algoritam bi se ubrzao nekoliko puta (predpostavljam). Postoji jos jedna varijanta, a to je da u vektoru pamtis sve proste brojeve koje si do sad pronasao. Time se dobija algoritam koji je po brzini brzi od onog prvog, sporiji od Eratostenovog sita, ali zauzima manje memorije, te moze da se koristi za generisanje vise brojeva nego Eratostenovo sito.

Moguce je iskoristiti sito da bi se dobili prosti brojevi do nekog broja, npr milion, a onda da se predje na varijantu sa pamcenjem pronadjenih prostih brojeva. Ma sve su to djecija posla

Che, che, che. Ovo ti je pascal a ne C++. Ovde sam napisao Size div 2 (ne sqrt(Size)). Mali lapsus. A sto se tice da se svaki put racuna, nije tako.

pokreni ovo:



i vidices da ce se petlja vrtiti 5 puta a ne beskonacno.

_________________
U raju je lijepo, ali u paklu je raja.

Grrrrr čime li se ti drogiraš da mi je znati ...

O cemu ti?

_________________
U raju je lijepo, ali u paklu je raja.

pa o drogiranju

R-tarde govorio sam ti za kod koji je napisao borisdj. Molim te da citas poruke jer u suprotnom me bespotrebno nerviras.