liczby pierwsze - ćwiczenia 1.doc

ALGORYTM SPRAWDZANIA LICZB PIERWSZYCH

WERSJA 1

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;   //wyzerowanie tablicy

czas=clock();

for(i=2;i<=n;i++){

p=1;

for(j=2;j<i && p==1;j++)    //szukamy podzielnika liczby

    if(i % j == 0) p=0;      //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}      //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;      //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 2

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;   //wyzerowanie tablicy

czas=clock();

for(i=2;i<=n;i++){

p=1;

for(j=2;j<i && p==1;j++)    //szukamy podzielnika liczby

    if(i % j == 0) p=0;      //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}    //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;        //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

//for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 3

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;   //wyzerowanie tablicy

czas=clock();

for(i=2;i<=n;i++){

p=1;

for(j=2;j<(i+1)/2 && p==1;j++)    //szukamy podzielnika liczby + polepszenie szybkości obliczania

    if(i % j == 0) p=0;      //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;} //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;         //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

//for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 4

//Pominiecie sprawdzania liczby 2 i zwiększenie szybkości liczenia

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;      //wyzerowanie tablicy

czas=clock();

if(n>=2) {ilosc=1; tab[2]=1; }

for(i=3;i<=n;i+=2){

p=1;

for(j=3;j<(i+1)/2 && p==1;j+=2)    //szukamy podzielnika liczby + polepszenie szybkości obliczania

    if(i % j == 0) p=0;      //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}      //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;      //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

//for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 5

//odkomentarzowanie for

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;     //wyzerowanie tablicy

czas=clock();

if(n>=2) {ilosc=1; tab[2]=1; }

for(i=3;i<=n;i+=2){

p=1;

for(j=3;j<(i+1)/2 && p==1;j+=2)    //szukamy podzielnika liczby + polepszenie szybkości obliczania

    if(i % j == 0) p=0;        //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}        //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;         //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 6

//korzystamy z pierwiastków żeby czas zmniejszyć obliczeń

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;     //wyzerowanie tablicy

czas=clock();

if(n>=2) {ilosc=1; tab[2]=1; }

for(i=3;i<=n;i+=2){

p=1;

for(j=3;j<=(int)sqrt(i) && p==1;j+=2)   //szukamy podzielnika liczby + polepszenie szybkości obliczania

    if(i % j == 0) p=0;        //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}      //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;       //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

    system("PAUSE"); return 0;

}

WERSJA 7

//zakomentarzowane for

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

int n, i, j, L, p, ilosc=0; long czas;

int main(){

printf("podaj N: "); scanf("%i", &n);

int *tab=new int[n+1];

for(i=1;i<=n;i++) tab[i]=0;       //wyzerowanie tablicy

czas=clock();

if(n>=2) {ilosc=1; tab[2]=1; }

for(i=3;i<=n;i+=2){

p=1;

for(j=3;j<=(int)sqrt(i) && p==1;j+=2)   //szukamy podzielnika liczby + polepszenie szybkosci obliczania

    if(i % j == 0) p=0;         //jeżeli reszta z dzielenia i/j=0

if(p==1) {ilosc++; tab[i]=1;}      //sprawdzanie czy pętla zakończyła się przed czasem.

}  //koniec for

czas=clock() -czas;      //od aktualnego czasu odejmuje poprzedni

printf("razem liczb pierwszych %i czas=%i\n", ilosc, czas);

//for(i=2;i<=n;i++) if(tab[i]) printf("%i, ",i);

printf("\n");

...