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:

1. #include <stdio.h>
2.  
3. void upis(int n,int *a){
4. int i=2;
5. for(;--n;a++,i++) *a=i;}
6.  
7. void sito(int n,int *a){
8. int i=2,j,k=0,l=n;
9. for(i=*a;--n;k++){
10.    for(j=i;j<l;j+=i) *(a+j)=0;
11.    if(*(a+k)) printf("%i ",*(a+k));}}
12.  
13. void main(){
14. int n,a[100];
15. scanf("%i",&n);
16. upis(n,a);
17. sito(n,a);
18. }

• 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: [Link mogu videti samo ulogovani korisnici]
Koristan sadržaj: [Link mogu videti samo ulogovani korisnici]

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.

[Link mogu videti samo ulogovani korisnici]

• 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

0. #include <stdio.h>
1. #include <math.h>
2.  
3. main(){
4.  
5.    int n;
6.    scanf("%i",&n);
7.    int niz[n],i,j;
8.    
9.    // Punjenje niza
10.    for(i=0; i <= n ; i++) {
11.       niz[i] = 1;
12.    }
13.    
14.    // Logika
15.    for (i=2; i <= sqrt(n); i++ )
16.       if (niz[i] == 1)
17.          for (j=i; j <= (n / i);j++ )
18.             niz[i*j] = 0;
19.    
20.    // Ispis
21.    for(i=0; i <= n ; i++) {
22.       if (niz[i] == 1)
23.          printf("%d \n", i);
24.    }
25.  
26. }

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

0. $ time ./prosti 1000000 > /dev/null
1.  
2. real    0m0.183s
3. user    0m0.152s
4. sys     0m0.008s
5.  
6.  
7. $ time primes 1 1000000 > /dev/null
8.  
9. real    0m0.090s
10. user    0m0.028s
11. sys     0m0.000s

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

0. int main()
1. {
2.   int n;
3.   cin>> n;
4.   bool ind = false;
5.   int i = 1;
6.   while( i <= n )
7.   {
8.     if( i <=3 )
9.        cout<< i;
10.     int j=2;
11.     while( j <= i/2 )
12.         if(( i % j) != 0 )
13.                j = j +1;
14.         else
15.                ind = true;
16.     if ( ! ind )
17.         cout<< i;
18.     i = i+1;     
19.   }
20.   return 0;
21. }