C/C++ program za racunanje N-tog rpostog broja

Evo ovako... napravija sam program koji za upisani n nade n-ti prosti broj...ali koristio sam polja pa tako da je maximum n zapravo maximum polja....

evo programa:

#include <stdio.h>

ako mozes pojasnit :D

moram pamtiti...

algoritam radi tako da eliminira brojeve sa znamenkom jedinice 2,4,5,6,8,0 medu svakih 10 brojeva i da provjeri ostale brojeve 1,3,7,9 da li su djeljivi sa proslim prostim brojevima....ovo je najbrzi nacin...puno je brze od gledanja svakog iduceg da li je djeljiv sa svim brojevima do njegovog broj/2 ....

otprilike shvacan ovo sa sqrt() ...

#include <stdio.h>

#include <conio.h>

#include <math.h>

main (){

    int a=21, i, br=0;

    for (i=2; i<=a/2; i++){

      if (a%i==0){

       printf("%d\n", i);

       br++;}

      }

    printf("\n%d\n\n", br);

    br=0;   

    for (i=2; i<=sqrt(a); i++){

      if (a%i==0){

       printf("%d\n", i);

       br++;}

      }

    printf("\n%d", br);

    getch();

    }

bool isprost(int n){

if( n == 2 || n == 3 ) return 1;

if( (n -1)%6 != 0 || (n+1)%6 != 0) return 0;

if( i % 2 == 0) return 0;

for( int i = 3 ; i < sqrt(n) +1 ; i=i+2) if(n % i == 0) return 0;

return 1;

}

nisam eliminira samo parne :DD eliminiraj i sve koji su djeljivi sa 5...

znaci sad mogu isti onaj moj kod di provjerava sve brojeve medu 10 brojeva sa znamenkama 1,3,7,9 i samo da provjeri jesu li djeljivi od 2 do sqrt(x)  :DD

eto kasnije cu napravit funkciju koja ce racunat nti prosti broj pa cu moc napravit i program koji rastavlja brojeve na proste faktore :D

Kako? xD

Moj ide za svaka 4 broja medu 10 brojeva i provjeraje "bivše" a tvoj ide za svaki I od 2 pa nadalje i provjeraje do sqrt()? :D

samo sta moj radi do 250 :'(

pogledaj moj malo bolje radi na principu b+=10 medu deset brojeva...te onda b+z[x] gdje je z[x] jedinice 1,3,7,9 tako da je tu eliminirano brojevi dijeljivi sa 2,5 :))) :PPP

evo poslusat cu vas :D

NOVI KOD:

#include <stdio.h>

#include <conio.h>

#include <math.h>

//Funkcija za provjeru jeli broj prost//

int prosti(int x){

   int i;

   if (x==2) return 1;

   if (x%2==0) return 0;

   for (i=3; i<=sqrt(x); i+=2)

     if (x%i==0) return 0;

   return 1;

   }

//Funkcija koja za uneseni n vrati n-ti prosti broj//

int nprosti(int x){

   int i=0, p=2;

   while (i<x){

      if (prosti(p)) i++;

      p++;

      }

   p--;

   return p;

   }

//Test Funkcije//

main (){

    int n;

    do {

     printf("Odaberi N [1<=N<=50000]: ");

     scanf("%d",&n);

     } while ( n<=0 || n>50000);

    printf("%d. prosti broj je %d", n,nprosti(n));

    getch();

    }

Pokušaj ovo, efektnije je od tolikih djeljenja:

class Program

   {

     static void Main(string[] args)

     {

       int broj = 739;

       BitArray niz = new BitArray(broj + 1, true);

       for (int i = 2; i <= broj; i++)

         if (niz[i])

         {

           for (int j = i * 2; j <= broj; j += i)

             niz[j] = false;

         }

       if (niz[broj])

       {

         Console.WriteLine("Broj je prost!");

       }

       else

       {

         Console.WriteLine("Nije prost broj!");

       }

     }

   }

Ovako napiši:

#include<stdio.h>

#include<stdlib.h>

int main()

{

int i, n, kontrolna = 1;

scanf("%d", &n);

for(i=2; i<=(n-1); i++)

{ if(n%i==0) {

   printf("Broj nije prost.");

   kontrolna = 0;

   break;

}

}

if (kontrolna)

printf("Broj je prost");

}

Radio si grešku u if else bloku, svaki put kad se izvrši petlja ti si izvršavao ili if ili else granu, zato se dešavalo da ti tako ispisuje

for(i=2; i<=(n-1); i++)

{ if(n%i==0)

   printf("Broj nije prost.");

   else

   printf("Broj je prost.");

}

getch();

Tu ti je bila greška, za svaku iteraciju petlje se izvršavao ili if ili else blok uvjetne naredbe, dakle za broj 4 ti se ovo desilo:

1. u prvoj iteraciji petlje ispituje se uvjet 4%2 == 0, pošto je true, program ispisuje "Broj nije prost"

2. u drugoj iteraciji petlje ispituje se uvjet 4%3 == 0, pošto je false, program ispisuje naredbu iz else bloka: "Broj je prost!".

Ako pogledaš što sam ja napravio bit će ti jasno kako ćeš "kontrolirati ispis", kako kažeš

U petlji sam ostavio samo if granu uvetne naredbe, i to tako da bude "ciao, nema više", čim se ispuni uvjet da je broj djeljiv sa

brojem ispod sebe, znači da nije prost broj, dalje mi petlja ne treba, i prekidam je sa naredbom break.

Kontrolna varjabla ima samo jednu svrhu, da se ispiše ili ne ispiše linija "Broj je prost!", a ta linija će se ispisati samo ako nijednom

tokom izvršavanja petlje nije uvjet n%i == 0 imao vrijednost true, odnosno ako broj nije djeljiv ni sa jednim brojem manjim od sebe,

dakle ako je prost broj.

Nisam puno gledao vase kodove, ali najbrzi (daleko) algoritam za trazenje prostih jes eratostenovo sito.

Algoritam radi na nacin da ides redom po nekom skupu brojeva, kada naiđeš na broj oznacis ga kao prostog i izbacis sve visekratnike toga broja iz skupa.

Istina je sto je Luuka rekao da to uzima puno memorije, ali dobivas na vremenu.

Nakon sto netko unese N, alociras polje na sljedeci nacin

int *A = new int[N+1] // C++

int *A = (int*)malloc( (N+1) * sizeof int )

Sve postavis na 1 i pises ostatak algoritma.

Evo kod na brzaka, mozda ima gresaka nije testiran ..

for ( int i = 2; i <= N; ++i )

  if ( prim[i] )

    for ( int j = 2*i; j <=N; j += i )

      prim[j] = 0;

Ovo se naravno moze jos optimizirati po potrebi ....

Mozda bi se moglo probati koristiti stl - set pa ustedjeti na memoriji.

Znam napisati veoma slozenu strukturu bitseta, kojom bi se također moglo uštedjeti na memoriji ...

Trebalo bi probati implementirati .......

Nazalost vrijeme bi bilo malo sporije od O(1) :(.

Ovaj kod je u potpunosti kriv.

1) Ti sigruno loopas samo jednom, jer radis break u oba slicaja, drugim rijecima program govori jeli broj paran ili ne.

2) Ne moras ici do N-1, vec do N / 2 odnosno do sqrt(N) ali to vise manje

Ono sto si htio jest ovo :

Broj je prost ako nema niti jednog manjeg od njega da je djeljiv.

bool prost = true;

for (int i = 2; i * 2 <= N && prost; ++i) {

  if (N % i == 0) prost = false;