21 kwietnia 2005 22:19Liczby pierwszePaweł Gniadkowski [Kardon] Zasada szukania liczb pierwszych jest następująca:
Tworzymy tablicę wartości logicznych indeksowaną od 2 do n, gdzie n jest limitem, dla jakiego będziemy szukać liczb pierwszych. Tablicę wypełniamy wartościami true. Kolejnym etapem jest wykreślanie liczb, które nie są liczbami pierwszymi poprzez oznaczanie odpowiadających im pól tabeli jako false. Wykreślanie odbywa się w następujący sposób: dla liczb od 2 do k (gdzie k to zaokrąglony w dół do całości pierwiastek kwadratowy z liczby n - limitu) wykreślamy wielokrotności tej liczby z tablicy. Wypisanie liczb pierwszych ogranicza się do wypisania indeksów pól tabeli, których wartość to true.
Trochę zagmatwałem opis algorytmu, ale po jego przestudiowaniu powinno sie rozjaśnić: #include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int i,zakres;
cout << "Jaki zakres mam przeszukac?" << endl;
cin >> zakres;
cout << endl;
bool tablica[zakres];
for (i=2;i<=zakres;i++)
{
tablica[i] = true;
}
int limit = sqrt(float(zakres));
for (i=2;i<=limit; i++)
{
if (tablica[i]!=false)
{
for (int j=i+1;j<=zakres;j++)
{
if (j % i==0)
{
tablica[j]=false;
}
}
}
}
cout << "Liczby pierwsze z zakresu od 1 do " << zakres << ":" << endl;
for (i=2;i<=zakres;i++)
{
if (tablica[i]!=false)
{
cout << i << endl;
}
}
}
Paweł Gniadkowski [Kardon]
