Liczby pierwsze C++

19Radek88 · Post autor: **19Radek88** » 10 gru 2007, o 23:47

Jak powinien wygladac kod w C++ do:

"Program wypisujący liczby pierwsze ze zbioru {1,2,3,...,n} (n podaje użytkownik)"

Pogubilem sie troche w petlach...

kadiii · Post autor: **kadiii** » 11 gru 2007, o 01:12

W necie jest tego masa. Poszukaj...(chociażby sito Eratostenesa )

1983 · Post autor: **1983** » 11 gru 2007, o 02:01

Wspomniane sito Eratostenesa:

Kod: Zaznacz cały

#include <iostream>
using namespace std;

int main() {

   cout << "Podaj zakres: ";
   int e; //Zakres
   cin >>e;
   cout << "W zakresie od 0 do "<< e <<" znalazlem nast. liczby pierwsze:
" << endl;
    
   int f=e/2;

   bool l[e];
   for(int i=0;i<e;i++) l[i]=1;

   for(int i=2;i<f;i++) // sito
     if(l[i]) for(int j=i+i;j<e;j+=i) l[j]=0;

   // wypisanie liczb pierwszych od 1 do e
   int count=0;
   for(int i=1;i<e;i++)
   { 
     if(l[i])
     {
        cout << i << "	";
        count++;
     }
   }
   cout << "

W sumie " << count << " liczb pierwszych" << endl;
system("pause");
return 0;
}

Rafal88K · Post autor: **Rafal88K** » 18 gru 2007, o 23:21

Przykro mi al Twój program jest źle napisany

1983 pisze:bool l[e];

Ciekawe jak chcesz, żeby to działało w trybie pełnej zgodności? Musisz tu skorzystać z pamięci dynamicznej i tablice umieścić na stercie, a nie na stosie.

Kod: Zaznacz cały

#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
    bool* t;
    int r;

    cin >> r;
    t = new bool[r];

    for(int i = 0; i < r; ++i)
    {
        t[i] = true;
    }

    for(int i = 0; i < r; ++i)
    {
        if(t[i])
        {
            cout << i + 1 << endl;
        }
    }

    system("pause");
    return 0;
}

DerSchmetterlig · Post autor: **DerSchmetterlig** » 26 gru 2007, o 00:27

Rafal88K Jak dla mnie to Twój program podaje wszystkie liczby od 1 do podanej, a nie tylko liczby pierwsze

Rafal88K · Post autor: **Rafal88K** » 26 gru 2007, o 01:58

DerSchmetterlig brawo, tylko on nie miał podawać liczb pierwszych tylko pokazać jak się poprawnie powinno alokować pamięć w C++

Może i chciałeś zabłysnąć ale nic z tego nie wyszło

DerSchmetterlig · Post autor: **DerSchmetterlig** » 26 gru 2007, o 02:14

Zabłysnąć nie za bardzo bo przed Tobą i tak jestem malutki :[

A Ty jedyne co zrobiłeś to "popisałeś" się przed kimś kto zrobił błąd, ale nie pomogłeś autorowi tematu

Undre · Post autor: **Undre** » 26 gru 2007, o 02:22

Rafal88K pisze:Może i chciałeś zabłysnąć ale nic z tego nie wyszło

Przyganiał kocioł garnkowi

Rafal88K · Post autor: **Rafal88K** » 26 gru 2007, o 10:58

DerSchmetterlig pisze: A Ty jedyne co zrobiłeś to "popisałeś" się przed kimś kto zrobił błąd, ale nie pomogłeś autorowi tematu

Autorowi tematu nie musiałem pomagać bo pomógł mu 1983, a ja tylko chciałem powiedzieć, że w tym programie źle zrobiona jest dynamiczna alokacja tablicy.

DerSchmetterlig zanim napiszesz odpowiedź na post to dokładnie przeczytaj i zastanów się co autor miał na myśli

Xitami · Post autor: **Xitami** » 27 gru 2007, o 21:09

Kod: Zaznacz cały

   for(int i=0;i<e;i++) l[i]=1;
   for(int i=2;i<f;i++) // sito
     if(l[i]) for(int j=i+i;j<e;j+=i) l[j]=0;

zero i jeden nie są liczbami pierwszymi, ale to drobiazg.
bardzo prosto da się to zrobić dowcipniej (szybciej).

Rafal88K · Post autor: **Rafal88K** » 27 gru 2007, o 22:00

Jeszcze lepiej zrobić tak:

Kod: Zaznacz cały

unsigned int i, j, pierwiastek;
pierwiastek = static_cast<unsigned int>(sqrt(static_cast<double>(e)));
for(i = 2; i <= e; ++i) l[i] = true;
for(i = 2; i <= pierwiastek; ++i)
{
    if(l[i])
    {
        for(j = i * i; j <= e; j += i)
        {
            l[j] = false;
        }
    }
}

Pisane bez testowania (bez kompilatora) więc mogą być literówki