Prosti brojevi

1

Prosti brojevi

offline
  • igor86  Male
  • Stručni saradnik
    Web programiranje
  • Pridružio: 24 Maj 2006
  • Poruke: 1633

Hajde ovako.
Ko ima primjere programa, koji pronalaze proste brojeve. Naravno, nista lakse? Ali cemo ici ka tome da se uz kod programa stave i rezultati dobijeni uz njega. Ici ka brzini izvrsavanja programa.



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • meka  Male
  • Počasni građanin
  • Pridružio: 06 Avg 2003
  • Poruke: 811
  • Gde živiš: Novi Sad / Vojvodina

Nemam ni jedan primer, ali evo jedne ideje. Prvo, osim 2, sve parne brojeve preskačeš pa inkrement u for/while petlji izgleda i+=2. Malo sam mozgao i stvarno mi ništa ne pada na pamet.



offline
  • Pridružio: 18 Dec 2003
  • Poruke: 7953
  • Gde živiš: Graceland

Najbolji algoritam je tzv. prosejavanje...

1 ne racunas, uzmes prvi sledeci:
2, odatle izbacujes svaki drugi: 4, 6, 8, 10..., uzimas prvi sledeci neizbaceni:
3, odatle izbacujes svako treci neizbaceni: 6, 9, 15... uzimas prvi sledeci:
5, izbacujes svaki peti...

offline
  • Pridružio: 16 Jun 2005
  • Poruke: 2392
  • Gde živiš: Beograd

@Leggy

To se zove eratostenovo sito, i meni je poznato kao najefikasniji algoritam. Moze se izvesti npr. ovako: #include <stdio.h> void upis(int n,int *a){ int i=2; for(;--n;a++,i++) *a=i;} void sito(int n,int *a){ int i=2,j,k=0,l=n; for(i=*a;--n;k++){    for(j=i;j<l;j+=i) *(a+j)=0;    if(*(a+k)) printf("%i ",*(a+k));}} void main(){ int n,a[100]; scanf("%i",&n); upis(n,a); sito(n,a); }

Ovo ovako napamet...

offline
  • Pridružio: 23 Jan 2004
  • Poruke: 43

Davno sam još pisao o Eratostenovom situ ovde na forumu... Samo da nađem temu!

Evo je: mycity.rs/Pascal/Prost-broj.html#285386
Koristan sadržaj: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Jedino što tad nisam dobrio pročitao temu, pa je ispalo da nije potrebno ovo, ali eto, može sad nekom poslužiti!

Dopuna: 08 Feb 2007 20:53

Citat:
Jump to: navigation, search

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes: the Atkin sieve does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes.


en.wikipedia.org/wiki/Sieve_of_Atkin

offline
  • meka  Male
  • Počasni građanin
  • Pridružio: 06 Avg 2003
  • Poruke: 811
  • Gde živiš: Novi Sad / Vojvodina

Problem kod njega su veliki nizovi koji pre ili kasnije postanu poprilično praznjikavi, pa sam mislio da je bolje generisati ih (u letu).

offline
  • igor86  Male
  • Stručni saradnik
    Web programiranje
  • Pridružio: 24 Maj 2006
  • Poruke: 1633

Evo mog primjera

#include <stdio.h> #include <math.h> main(){    int n;    scanf("%i",&n);    int niz[n],i,j;        // Punjenje niza    for(i=0; i <= n ; i++) {       niz[i] = 1;    }        // Logika    for (i=2; i <= sqrt(n); i++ )       if (niz[i] == 1)          for (j=i; j <= (n / i);j++ )             niz[i*j] = 0;        // Ispis    for(i=0; i <= n ; i++) {       if (niz[i] == 1)          printf("%d \n", i);    }   }

Jako brzo radi, samo hocu napraviti da radi na nivou bita, a ne na nivou byta.

offline
  • meka  Male
  • Počasni građanin
  • Pridružio: 06 Avg 2003
  • Poruke: 811
  • Gde živiš: Novi Sad / Vojvodina

Napravi da je bool niz[n]. Malo manje zauzima a radi ono što ti treba.

offline
  • Pridružio: 23 Jan 2004
  • Poruke: 43

Koliko ja znam C nema bool kao tip podataka! Ali može da stavi byte...

$ time ./prosti 1000000 > /dev/null real    0m0.183s user    0m0.152s sys     0m0.008s $ time primes 1 1000000 > /dev/null real    0m0.090s user    0m0.028s sys     0m0.000s

Program primes je program koji isto traži sve proste brojeve u intervalu i ispisuje ih. Iz ovog što sam priložio se vidi da primes radi brže, a on koristi Eratostenovo sito. Do duše primes koristi veliki broj prethodno izračunatih prostih brojeva, pa je vrlo verovatno da zbog toga brže radi, ali nisam se dublje upuštao u kod.

btw. modifikovao sam igorov program da prima n kao parametar radi lakšeg merenja.

offline
  • Pridružio: 21 Nov 2007
  • Poruke: 14

Svaki broj n deljiv je brojem 1, samim sobom i nekim brojem iz intervala od 2 do n div 2 ( pri cemu je div operacija celobrojnog deljenja).

Prema tome, n je deljivo sa [1],[2,n div 2],[n]

Prost broj p je broj koji je deljiv iskljucivo brojem 1 i samim sobom.

Prema tome, p je deljivo sa [1],[p]

Zadatak glasi:

Stampati sve proste brojeve od 1 do n, pri cemu n unosi korisnik.


Da bi smo resili ovaj zadatak moramo uvesti petlju koja ce da vrti sve prirodne brojeve od 1 do n.Algoritam potom za svaki prirodni broj iz tog intervala proverava da li taj konkretni prirodni broj ima bar jednog delitelja u intervalu od 2 do n div 2. Ukoliko postoji bar jedan delitelj u tom intervalu, za konkretan prirodni broj, broj nije prost. Ukoliko ne postoji ni jedan delitelj u intervalu od 2 do n div 2 broj je prost i mozemo izvrsiti njegovo stampanje.


(Operacija div u C++, oznacava se sa / samo sto se vrsi nad celobrojnim operandima.Operacija moduo u C++ je predstavljena simbolom %, i rezultat te operacije je ostatak celobrojnog deljenja nad operandima nad kojima se operacija izvrsava. Tako broj i ce biti deljiv brojem j ukoliko je ispunjen uslov i % j == 0 ).


                                                  int main() {   int n;   cin>> n;   bool ind = false;   int i = 1;   while( i <= n )   {     if( i <=3 )        cout<< i;     int j=2;     while( j <= i/2 )         if(( i % j) != 0 )                j = j +1;         else                ind = true;     if ( ! ind )         cout<< i;     i = i+1;        }   return 0; }       

Ko je trenutno na forumu
 

Ukupno su 937 korisnika na forumu :: 48 registrovanih, 7 sakrivenih i 882 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: A.R.Chafee.Jr., amaterSRB, Atomski čoban, BSD, Cufo, darcaud, dekao, dozorni, dukikan, Georgius, Jovan Nenad, kovinacc, laki_bb, Leonardo, lovac12, lukac, macedonian45mk, madza, mačković, mercedesamg, mikrimaus, milos.cbr, Mirage 2000N, naki011, nemkea71, nuke92, oldtimer, pedja63, raskoljnikov, Recce, royst33, sabros, samo opusteno, segax1, Sirius, theNedjeljko, Toni, trajkoni018, vasa.93, vathra, virked, VJ, vobo, vsn111, willie, Zi0mek, zixmix, |_MeD_|