С клавиатуры вводится число N (типа int). Используя алгоритм «Решето Эратосфена», необходимо найти все простые числа (т.е. делящиеся только на себя и на единицу) в интервале [0;N].

// prime.cpp: определяет точку входа для консольного приложения.
 
#include "stdafx.h"
#include <iostream>
#include <iomanip> // содержится прототип манипулятора setw()
using namespace std;
 
int main(int argc, char* argv[])
{
    setlocale(LC_ALL, "rus");
    int n; // правая граница интервала
    cout << "Введите число - N: ";
    cin >> n;
 
    int size_array = n - 2; // так как первое простое число - это 2, то размер массива уменьшаем на 2, так как 0 и 1 не в счёт     
    int *arrayPtr = new int [size_array]; // создаём одномерный динамический массив размером n - 2
 
    for(int counter = 0; counter <= size_array; counter++)
    {
        arrayPtr[counter] = counter + 2; // записываем в массив все числа в интервале [2;n]
    }
    int p = 2; // первое простое число
    int index = 0; // переменная  для прохода по элементам массива
 
    // в цикле while реализовано решето Эратосфена
    while (p < n) // пока значение переменной p меньше введённого n
    {
        // в цикле for отсеиваем составные числа
        for (int counter = p*p - 2; counter <= size_array; counter += p)
        {
            arrayPtr[counter] = -1; // на места составных чисел присваиваем значение -1
        }
 
        // в цикле while изменяем значение переменной p
        while (arrayPtr[index] <= p ) // пока значение из массива чисел меньше либо равно значению переменной p
        {
            index++; // переключаться на следующий элемент массива
        }
        p = arrayPtr[index]; // нужное значение массива найдено, поэтому присваеваем его переменной p
    } // конец алгоритма Эратосфена
 
    // вывод на экран простых чисел
    for(int counter = 0; counter <= n - 2; counter++)
    {
        if (arrayPtr[counter] != -1) // если элемент масссива не равен -1
        cout << setw(2) << arrayPtr[counter] << " "; // сделать вывод на экран
    }
 
    cout << endl;
    system("pause");
    return 0;
}

Добавлено: 11 Апреля 2018 10:31:16 Добавил: Андрей Ковальчук Нравится 0

Добавить