Лаба №1. Обзор языка программирования С [Вариант 4]

Дата: Ср, 03/24/2010 - 05:49; Автор: House M.D.
Вариант: 
4
Решение

 #include "math.h"

#include <iostream>
#include "conio.h"
using namespace std;
 
/*
 
Решето Эратосфена для нахождения простых чисел 
 
В последовательности чисел 2, 3, ..., n последовательно вычеркиваем каждое второе число после 2. 
Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. 
Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор,
пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n, неравное 1,
не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, 
которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.
*/
 
void main()
{
int i,j,m;
int a[100];
bool success=false;
 
for (i=3; i<=100; i++) a[i]=i;
a[0]=0; a[1]=0;
cout << "vvedite M" << "\n";
while(!success)  
{  
cin >> m;        
if(cin.good()){
success = true;
}  
else{ 
   cout << "nevernoe znachenie" << "\n"; 
    cin.clear();
    _flushall();
}
}
 
if (m<2) cout << "prostih 4isel menshe 4em " << m <<" netu" << "\n";
for (i=2; i<=sqrt(m); i++){
if (a[i]){
for (j=i*i; j<=m; j=j+i) a[j]=0;
}
}
cout << "result: ";
for (i=2; i<=m; i++){
if (a[i])  cout <<a[i] << " ";
}
cout << "\n";
getch();
}
 
Файл с решением: 
application/zip иконкаLab1v4.zip
Задание

Напечатать все простые числа, не превосходящие заданное число M. Для ускорения вычислений полезно завести таблицу для уже найденных простых чисел и проверять делимость очередного числа на числа из этой таблицы. Четные числа, естественно, не рассматривать. Таблица понадобится менее чем на элементов.