29-4 غربال اراتستن

(غربال اراتستن)یک عدد صحیح اول عددی است که فقط بر خود و بر 1 بخش پذیر باشد. غربال اراتست روش برای یافتن اعداد اول می باشد. این روش به شکل زیر اجرا می شود:

الف) ارایه ای در نظر گرفته و مقدار اولیه ی تمام عناصر ارایه را برابر  1 (true) قرار دهید. در نتیجه عناصر با اندیس اول 1 باقی مانده خواهند ماند ولی بقیه ی عناصر ارایه صفر می شوند.

ب) با شروع از اندیس 2 (اندیس 1 حتما اول است.) هر دفعه که عنصری با مقدار 1 پیدا شود در بقیه ارایه عناصری که اندیس ان ها مضربی از اندیس عنصر با مقدار 1 است صفر می شوند. برای اندیس 2 همه ی عناصر بعد از 2 که اندیس ان ها مضربی از 2 است(اندیس های 4 6 8 و...) برابر با صفر می شوند. برای اندیس 3 همه ی عناصر بعد از 3  که اندیس ها یشان مضربی از 3 است(اندیس های 6 9 12 15 و...) صفر می شوند. و به همین ترتیب در پایان عملیات عناصری از ارایه که هنوز یک هستند اندیس هایی را نشان می دهند که ان ها عدد اولند. حال برنامه ای بنویسید که اعداد اول 1 تا 999 را با استفاده از یک ارایه ی 1000 عنصری یافته و ان ها را نمایش دهد. عنصر صفر ارایه را نادیده بگیرید.

 #include<iostream>

#include<conio.h>

#include<iomanip>

using namespace std;

int main()

{

const int SIZE = 1000;

int array[SIZE], count = 0;

for(int k = 1; k < SIZE; ++k )

array[k] = 1;

for(int i = 1; i < SIZE; ++i)

if(array[i] == 1 &&  i != 1)

for(int j = 1; j <= SIZE; ++j)

if(j % i == 0 && j !=i)

array[j] = 0;

//range 2 - 197

for(int q = 2; q < SIZE; ++q)

if(array[q] == 1) {

cout << setw(3) << q << " is a prime number.\n";

++count;

}

cout << "A total of " << count << " prime numbers were found." << endl;

getch();

return 0;

}