C++ - Wypisywanie liczb pierwszych mniejszych od podanej liczby a?

[nyac55]

Witam. Mam do wykonania program ,który wypisuje wszystkie liczby pierwsze ,które są mniejsze od podanej z klawiatury liczby a. Czy ktoś pomoże mi skonstruować ten program??

[[Ekspert] Hakken]

Jakiego rzędu jest ta liczba? Jeśli stosunkowo niewielka to możesz użyć sita Eratostenesa.

[nyac55]

Liczbę podaje użytkownik ,więc nie wiadomo( może być dowolna). Możesz wrzucić jakiś przykładowy kod jak miałoby to wyglądać z "sitem"?

[mateusz(stefan)]

http://bit.ly/1784aNg

[[Ekspert] Hakken]

Liczbę podaje użytkownik ,więc nie wiadomo( może być dowolna)

Stwierdzenie czy dowolna liczba jest liczbą pierwszą jest bardzo złożonym problemem i opiera się na tym bardzo duża część współczesnej kryptografii. Algorytmy które to robią są albo powolne, albo zżerają masę pamięci, więc jeżeli chodzi ci o liczby rzędu 10^30 to będzie ciężko. W dość rozsądnym czasie można sprawdzić czy liczba jest pierwsza tak gdziś do... no nie wiem, 10^7?

Ważne jest też zastanowienie się, czy liczba może mieć jakiś dzielnik większy niż pierwiastek z tej liczby. No i jak zawsze polecam google, tam znajdziesz wytłumaczenie algorytmu i przykładowe implementacje.

[nyac55]

Znalazłem coś podobnego ,drobna modyfikacja i program działa poprawnie:

#include <iostream>
using namespace std;
   bool tablica[20000000];
int main()
{
   int n,licznik=0;
   cout << "Podaj n: ";
   cin >> n;
   n--;	   //liczbę n zmniejszamy o 1 ,bo liczby pierwsze muszą być mniejsze od podanej liczby "a"
   for(int i=0; i<=n; i++)
   {
	  tablica[i]=1;		    // wstepne przygotowanie tablicy
   }
   for(int j=2; j<=n; j++)
   {
	  int k=j;
	  while(k<n)
	  {
		  k=k+j;			    // wielokrotnosc danej liczby
		 tablica[k]=0;		  // wyzerowanie wielokrotnosci
	  }
   }
   for(int m=2; m<=n; m++)
   {
	  if (tablica[m]==1)		   // sprawdzamy, czy m-ty wuraz tablicy jest liczba pierwsza
	  {
		 cout << m << endl;	   // jezeli tak, to wypisujemy
		 licznik++;			 // ile liczb pierwszych?
	  }
   }
   cout << endl << "W zakresie od 0 do " << n << " znajduje sie " << licznik << " liczb pierwszych mniejszych od podanej liczby n wypisanych powyzej." << endl;
   return 0;
}

[Sevard]

Zamiast inta lepiej jest użyć uinta. I tak nie potrzebujesz znaku.

Jaki jest zakres wartości inta i jak się to ma do wielkości tablicy? Sprawdź co się stanie, jeśli n będzie więszke niż wielkość tablicy (powiedzmy 40000000).

Przy sicie Eratostenesa wystarczy sprawdzać wielokrotności liczb mniejszych bądź równych pierwiastkowi z n (dowód tego faktu zostawiam jako łatwe ćwiczenie), czyli linię

for(int j=2; j<=n; j++) 

można nieco zoptymalizować.