Program, Ktory Wypisuje Liczby Pierwsze

[kukus]

Od razu na wstepie chcialbym zaznaczyc ze nie prosze was o pomoc z powodu pracy domowej, konkursu ani zadnej z tych zeczy. Jestem bardzo poczatkujacy w pisaniu w C++. Mam taki kod:

 

#include <iostream>

 

using namespace std;

 

int main()

{

for (unsigned int i=3;i<=170000000;++i)

{

if ((i%4 || i%5 || i%3 || i%7)==0)

{

cout <<i;

cout <<" ";

}

else

{

cout <<"";

}

}

/*

 

*/

 

cout <<"\nNacisnij ENTER aby zakonczyc...\n";

getchar();

return 0;

}

 

Jak powinien wygladac kod?

Z góry dzięki.

Edytowane 5 Marca 2005 przez kukus

[edzinx]

#include <stdio.h>#include <math.h>int main(void){long i,j,t,x,h=2,n=1000000;long tablica[1000000];t=floor(sqrt(n));while( h<t) { i=h*h; while( i<n ) { tablica=1; i+=h; }doh++;while (tablica[h]!=0); } scanf("%ld",&j);for (i=1; i<=j; i++){scanf("%ld",&x); if (tablica[x]!=1) { printf("TAK\n"); } else printf("NIE\n"); }return 0;}

[kukus]

hymmm. To jest C? Niestety nie znam C i nie mam kompilatora do niego (chyba ze gdzies jest w Borland C++ Build).

[sp00n]

#include <iostream.h>#include <conio.h>#include <math.h>main(){        int n,i,j,*pierwsze;        cout<<"Podaj liczbe: ", cin>>n;        pierwsze = new int [n+1];        for (i=2;i<=n;i++) pierwsze[i]=1;        for (i=2;i<sqrt(n);i++)            if (pierwsze[i])                for (j=2*i;j<=n;j+=i) pierwsze[j]=0;        for (i=2;i<=n;i++) if (pierwsze[i]) cout<<i<<"\t";        delete pierwsze;        getche();}

to jest prosty programik wykorzystujący algorytm sita. Edytowane 5 Marca 2005 przez sp00n

[kukus]

THX wszystkim za pomoc ale jakos sam sobie poradzilem (az sam sie dziwie:D).Dalem taki kod:

 

#include <iostream>

 

using namespace std;

 

int main()

{

cout <<"2 3 5 7 11 ";

for (unsigned int i=3;i<=1700;++i)

{

if ((i%3)==0)

{

}

else if ((i%2)==0)

{

}

else if ((i%5)==0)

{

}

else if ((i%7)==0)

{

}

else if ((i%11)==0)

{

}

else

{

cout <<i;

cout <<" ";

}

}

/*

 

*/

 

cout <<"\nNacisnij ENTER aby zakonczyc...\n";

getchar();

return 0;

}

[sp00n]

Ten twój program wypisuje nie tylko liczby pierwsze :)

np. 1157 i 1691 nie są takimi liczbami. To takie wzięte pierwsze z brzegu.

Edytowane 5 Marca 2005 przez sp00n

[Polar]

Kiedyś napisałem taki program, może ci sie przyda oto jego kod.

 

#include <iostream>#include <cstdlib>#include <ctime>using namespace std;int main(){  cout << "Program do wyszukiwania liczb pierwszych\n\n"       << "Podaj przedzial liczb do wyszukania:" << endl;  uint64_t  ile = 0, ile1 = 0  , suma = 0 , odd  , suma1 = 0 , od , doo;  cout << "od - ";  cin >> od;  odd = od;  cout << "do - ";  cin >> doo;  cout << endl;  clock_t start, end;  start = clock();   // czas start!!!  for (uint64_t i = od; i < doo+1 ; i++)  {     uint64_t dzielnik = 2;     while ((dzielnik < i) && ((i % dzielnik) != 0)) dzielnik++;     if (dzielnik == i)     {        ile++;                     suma += i;                 cout << i << endl;      }     else     {       ile1++;       suma1 +=i;       cout << "\t" << i << endl;     }  }  end = clock();  // czas stop!!!  cout << endl << "Wybrany przedzial " << odd << " - " << doo        << endl << "--------------------------" << endl       << "Ilosc liczb pierwszych - " << ile << endl        << "Suma liczb - " << suma << endl;  cout << "\nIlosc liczb pozostalych - " << ile1 << endl        << "Suma liczb - " << suma1 << endl << endl         << "Czas obliczen = " << (end - start) / CLK_TCK << 's'<< endl << endl; system("pause");  return 0;}

Program był komopilowany pod DevC++

Edytowane 6 Marca 2005 przez razor1

[Laptok]

Mam prosbe - jak taki program do wypisywania liczb pierwszych z jakiegos przedzialu bedzie wygladac w jezyku progr. JAVA

[yasin]

stworzenie algorytmu na znaleznie liczb pierwszych nie jest takie trywialne jak wam sie wydaje, a juz napewno nie jest latwe stworzenie takiego algorytmu o wielomianowym czasie zlozonosci, a tylko takie algorytmy maja sens, w przypadku algorytmu o czasie wykladniczym, na jakiekolwiek sensowne rezultaty bedziecie czekac cale zycie :)

[jg5]

#include <stdio.h>#include <conio.h>#include <time.h>int main(){int a,b,c,i,j,x,time,time1,time2,m;printf("Podaj zakres szukania liczb pierwszych\n");printf("OD: ");scanf("%d", &x);printf("DO: ");scanf("%d", &j);time1 = clock();for (a=x;a<=j;a++)    {        for (i=2;i<a;i++)         {          b = a % i;          if (b==0) c++;             if (c!=0) break;         }     if (c<1) printf("%d\n", i);     c=0;    }time2 = clock();time = time2- time1;printf("\nCzas: %d", time);getch();}

Teraz coś takiego spłodziłem... Program wypisuje liczby pierwsze z podanego zakresu, dokłanie nie wiem czy działa w 100% poprawnie. Dodatkowo użyłem tez <time.h> clock(); aby zmierzyć czas liczenia liczb pierwszych, taki lekki benchmark ;)

Dla athlona 2Ghz liczenie liczb pierwszych z zakresu 1 - 100000 zajmuje około 12788 czyli prawie 13sekund.

Kompiluje się to pod Borland C++ oraz Dev C++, po lekkich zmianach tez pod Visual C++. Widać wtedy jak na dłoni który kompilator generuje optymalniejszy kod, róznice są duuże przynajmniej w tym programie sięgają nawet 50%.

Bardzo też ciekawe jest to ze celerony liczą to bardzo szybko. celina 1,8Ghz bierze spokojnie antka 2Ghz. Dokłanie nie wiem czym to jest spowodowane ale chyba intele lepiej sobie radzą z niektórymi operacjami.

 

To co wyzej tylko skapilowane

 

EDIT:

 

Dodam ze program jest cholernie nie optymalny i liczenie dużych liczb pierwszych nie ma sensu, algorytm sita przedstawiony wyżej przez sp00n jest o wiele szybszy.

Edytowane 26 Maja 2005 przez jg5

[civi]

stworzenie algorytmu na znaleznie liczb pierwszych nie jest takie trywialne jak wam sie wydaje, a juz napewno nie jest latwe stworzenie takiego algorytmu o wielomianowym czasie zlozonosci, a tylko takie algorytmy maja sens, w przypadku algorytmu o czasie wykladniczym, na jakiekolwiek sensowne rezultaty bedziecie czekac cale zycie :)

1465775[/snapback]

Powiadasz wykładniczym ? znasz jakiś taki algorytm ? nawet dzielenie przez wszystkie liczby całkowite od 2 do n ma złożoność liniową. Sito ma o ile pamiętam n log(log n) dla znalezienia liczb pierwszych z przedziału [1..n]. Działa naprawdę szybko. Do dość szybkiego znalezienia liczb pierwszych w przedziale może posłużyć ten nieco brzydki i napisany dokładnie tak jak nie powinien być napisany program:

#include <stdio.h>#include <math.h>#include <string.h>#define sqr(a) (int)sqrt((double)(a)) char P[100001], S[100001];int  O[100001], top;int main(){    int a, b, t;    int ta, tp, i ,j;    scanf("%d",&t);    while(t--)    {        memset(P,0,sizeof(P));        memset(S,0,sizeof(S));        top = 0;        scanf("%d %d",&a,&b);        ta = sqr(b) + 1;        tp = sqr(ta+1) + 1;        for(i=2;i<=tp;i++) if( S[i]==0 )            for(j=i<<1;j<=ta;j+=i) S[j] = 1;        for(i=2;i<=ta;i++)        {            if(S[i]) continue;            j = a - (a%i);            if(j==0) j=2*i;            if(j<a || j==i || a==i) j += i;            for(; j <= b; j += i ) P[j-a] = 1;        }        if(a==1) P[0]=1;        for(i=0,tp=b-a;i<=tp;i++)            if(!P[i]) printf("%d\n",i+a);        puts("");    }    return 0;}

EDIT: format wejścia:

<liczba przedziałów>

i potem liczby a i b określające początek i koniec każdego przedziału

Edytowane 27 Maja 2005 przez civi

[Gogiel]

Najprosciej jest to zrobic przy pomocy 2 petli for i modulo (%).

[ULLISSES]

Wszystko fajnie, ale jesli bedziecie uzywac juz istniejacych typow zmiennych - nawet int64, to liczenie bedzie sztuka dla sztuki, bo te wszystkie liczby juz dawno sa odkryte. Mysle, ze tu chodzi o samo zauwazenie, jak dziala algorytm i o nauke programowania. Dyskusje na temat ich szybkosci mozna sobie w tej chwili odpuscic...

[jg5]

Na odkrycie największej liczby pierwszej i tak nie mamy co liczyć na domowych komputerach.

A szukanie coraz bardziej optymalnego algorytmu moze być ciekawe i pouczające, i jest niezła satysfakcja jak się uda przyśpieszyć program kilkakrotnie. W sumie w programowaniu nie sztuka napisać program, tylko sztuka napisać tak aby działał wmiare szybko.

[civi]

https://spoj.sphere.pl/problems/PRIME1/ jakbyście chcieli potestować wydajność napisanego przez siebie programu. Polecam nie używać iostreamow :)