[C++] Program znajdujący liczby pierwsze

ptasiek123 · Post autor: **ptasiek123** » 7 lis 2011, o 22:00

progrem ma pokazac liczby pierwsze 1-liczba pierwsza 0-nie

#include <iostream>
#include<iomanip>
using namespace std;
int main()
{
    const int NMAX=400;
    int n;
    cout<<"Podaj ilosc liczb : ";
    cin>>n;
    int LICZBY[NMAX];
    int FLAGA[NMAX];
    for(int i=0; i<n;i++) {
            LICZBY[i]=i+1;
            FLAGA[i]=1;
            }
            FLAGA[0]=0;
                 for(int i=2;i<n;i++){
                    for (int p=2;p<=i;p++){
                        
                        FLAGA[p*i-1]=0;}}
      
        for(int i=0;i<n;i++)
    {
        cout<<LICZBY[i]<<"               "<<FLAGA[i]<<endl;}
       
    system("pause");
    return 0;
}

i mam taki problem gdyz flaga wychodzi mi za zakres i pokazuje 30 liczb i niektore zamiast numeru liczby maja zero
nie wiem gdzie mam umiescic "p*i-1" aby nie wychodzilo za zakres
z góry dzieki za pomoc

adambak · Post autor: **adambak** » 7 lis 2011, o 22:45

Trochę Ci uporządkowałem kod:

Kod: Zaznacz cały

#include <iostream>
#include<iomanip>
using namespace std;
const int NMAX=400;
int LICZBY[NMAX];
int FLAGA[NMAX];
int main()
{
  int n;
  cout<<"Podaj ilosc liczb : ";
  cin>>n;
  for(int i=0; i<n;i++)
  {
    LICZBY[i]=i+1;
    FLAGA[i]=1;
  }

  FLAGA[0]=0;
  for(int i=2;i<n;i++)
    for (int p=2;p<=i;p++)
      FLAGA[p*i-1]=0;

  for(int i=0;i<n;i++)
    cout<<LICZBY[i]<<" "<<FLAGA[i]<<endl;

  return 0;
}

myślę, że teraz trochę bardziej widać co i jak..
nic dziwnego, że wychodzi poza zakres, weź \(\displaystyle{ n=30}\), wtedy będzie w którymś kroku pętli \(\displaystyle{ p\cdot n > NMAX}\), a więc Segmentation Fault.. może napisz co to za metoda, którą masz polecenie znaleźć liczby pierwsze? bo nie bardzo rozumiem, Twoja własna? kilka modyfikacji i mamy sito Eratostenesa, które będzie działać dobrze, ale nie wiem po prostu czy tego chcesz, czy ma to być inaczej..

-- 7 lis 2011, o 23:51 --

ok, mam:

Kod: Zaznacz cały

#include <iostream>
#include<iomanip>

using namespace std;

const int NMAX=400;

int LICZBY[NMAX];
int FLAGA[NMAX];

int main()
{
  int n;
  cout<<"Podaj ilosc liczb : ";
  cin>>n;
  for(int i=1; i<=n;i++)
  {
    LICZBY[i]=i;
    FLAGA[i]=1;
  }

  FLAGA[0]=0;
  FLAGA[1]=0;
  for(int i=2;i*i<=n;i++)
   if(FLAGA[i]==1)
     for (int p=i+i;p<=n;p+=i)
       FLAGA[p]=0;

  for(int i=1;i<=n;i++)
    cout<<LICZBY[i]<<" "<<FLAGA[i]<<endl;

  return 0;
}

może być?
zauważ że teraz robimy tylko do \(\displaystyle{ \sqrt{n}}\) pierwszą pętlę a więc optymalniej.. ponadto do komórek w tablicy FLAGA odwołujemy się za pomocą tylko zmiennej p (co ułatwia sprawę) i o której wartościach wiemy wszystko - nie przekroczymy zakresu, nie będzie błędu.. chyba działa całkiem ładnie..

-- 7 lis 2011, o 23:53 --

wszystko jasne? jeśli coś nie jest, to pytaj śmiało..-- 8 lis 2011, o 00:00 --zauważ, że tablica LICZBY przy tym wariancie jest zupełnie zbędna, bowiem LICZBY = i i to nam wystarczy..

ptasiek123 · Post autor: **ptasiek123** » 7 lis 2011, o 23:15

wielkie dzieki
ja dopiero zaczynam programowac wiec starczy mi tak jak jest:)
jeszcze raz dzieki

Xitami · Post autor: **Xitami** » 8 lis 2011, o 02:51

Kod: Zaznacz cały

    ...
    cin >> n;
    int * flaga = new int [n];
    ...
            for( p= i*i ; ...
    ...

ptasiek123 · Post autor: **ptasiek123** » 9 lis 2011, o 15:37

Napisać program który z zadanego z zbioru kolejnych liczb naturalnych wypisze wszystkie liczby pierwsze.
Krok 0
Tworzymy dwie tablice o rozmiarach 1xN (liczby, flagi). Pierwsza tablicę wypełniamy kolejnymi N liczbami naturalnymi. Z kolei druga tablica zawierać będzie informacje czy dana liczba jest liczba pierwszą „1” czy nie „0”. Na początku wszystkie komórki tej tablicy ustawiamy na wartość „1”.
Krok 1
usuwamy liczbę 1, która nie jest liczba pierwszą, wypisując wartość „0” do odpowiedniej komórki macierzy flaga(flaga[0]=0).

Liczby 1 2 3 4 5 6 7 8 9
flagi 0 1 1 1 1 1 1 1 1

Krok 2
Liczbę 2 zapisujemy jako liczbę pierwszą (niezmieniany wartości odpowiadającej jej komórki macierzy flaga[1]). Usuwamy liczby stanowiące wielokrotność 2, które nie SA liczbami pierwszymi poprzez ustawienie odpowiednich komórek macierzy flaga na wartość „0”(flaga[n*2-1]=0, n= 2,3,4…)

Liczby 1 2 3 4 5 6 7 8 9
flagi 0 1 1 0 1 0 1 0 1

Krok 3
liczbe 3 zapisujemy jako liczbe pierwsza (wartość komorki w macierzy flaga odpowadaaca tej liczbie pozotyaje niezmieniona – flaga[2] =1). Usuwamy liczby stanwące wielokrotność 3, które nie są liczbami pierwszymi poprzez usuwanie odpowiednich Komorek macierzy flaga na wartość „0” (flaga[3*n-1] = 0, n= 2,3,4…)

Liczby 1 2 3 4 5 6 7 8 9
flagi 0 1 1 0 1 0 1 0 0

Kolejna liczbe ze zbioru zapisujemy jako liczbe pierwsza ( niezmieniany waqrtosci odpowiadającej jej komorki macierzy flaga). Usuwamy liczby stanowiace jej wielokrotność które nie s aliczbami pierwszymi.

oto tresc tego zadania i nie wiem czy ten kod bedzie dobry

adambak · Post autor: **adambak** » 9 lis 2011, o 17:16

jest wporządku, czyli jakaś tam odmiana sita Eratostenesa.. w którym miejscu masz wątpliwości czy to pasuje?

Kod: Zaznacz cały

  for(int i=1; i<=n;i++)
  {
    LICZBY[i]=i;
    FLAGA[i]=1;
  }

  FLAGA[0]=0;
  FLAGA[1]=0;
  for(int i=2;i*i<=n;i++)
   if(FLAGA[i]==1)
     for (int p=i+i;p<=n;p+=i)
       FLAGA[p]=0;
}

wyróżniłem tą właściwą część programu, czyli sam algorytm..
1) w wierszach 1-5 tworzymy zadaną tablicę liczb oraz tablicę flag.. na razie według flag wszystkie liczby są pierwsze..
2) w wierszach 7-8 ręcznie ustawiamy że zero i jeden nie są pierwsze, żeby nam nie psuć porządku..
3) wiersz 9: lecimy od dwójki (pierwsza liczba dla której teraz flaga wskazuje że jest pierwsza) do pierwiastka z maksymalnej liczby (dlaczego możemy tylko do pierwiastka i będzie dobrze?)
4) wiersz 10: spawdzamy czy liczba jest pierwsza według flagi, tzn czy nie została jeszcze skreślona, jeśli tak to wykonamy drugą pętlę.. jeśli nie - to nie ma sensu bo skoro jest złożona to została już wykreślona jako wielokrotność innej liczby (czyli nie jest pierwsza) a tymbardziej zostały wykreślone jej wielokrotności..
5) wiersze 11-12: lecimy w pętli do maksymalnej wartości od najmniejszej wielokrotności liczby \(\displaystyle{ i}\) - o której wiemy że jest pierwsza (wczesniejszy if), tak żeby jej samej nie wykreślić (nadać fladze wartość zero).. wykreślamy wszystkie wielokrotności w tym przedziale (do n) dlatego licznik w każdym kroku pętli zwiększamy o tą liczbę (bo jej wielokrotności nie są pierwsze)..
6) działa..

się powtórzę: pisz jeśli coś niejasne i dlaczego jest niejasne..