Prosti brojevi

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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