С клавиатуры вводится число
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;
}
CppStudio.com
Введите число - N: 30 2 3 5 7 11 13 17 19 23 29
Комментарии
art_h4rd
#include <iostream> #include <math.h> using std::cout; using std::cin; using std::endl; void del(int * mas, int index, int & size) { for (int i = index; i < size; i++) { mas[i] = mas[i + 1]; } size--; } int main() { int limit; cout << "limit: "; cin >> limit; limit--; int * arr = new int[limit]; for (int i = 0; i < limit; i++) { arr[i] = i + 2; cout << arr[i] << ' '; } cout << endl; bool work = true; auto * p = arr; int trash{}; while (work) { for (int i = trash + 1; i < limit; i++) { if (arr[i] % *p == 0) { del(arr, i, limit); } } if (*p > sqrt(limit)) { work = false; } p++; trash++; } for (int i = 0; i < limit; i++) { cout << arr[i] << ' '; } delete[]arr; return 0; }Вячеслав Перский
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { setlocale(LC_ALL, "rus"); vector <int> comp; vector <int> filter; int max,i2,fr,p=2,conc=0; cout << "Введите максимальное значение: "; while (cin >> max) { // Ввод макс. значения while( p*p < max - 2) { //выполняется до тех пор пока p квадрат меньше мкс. значения i2 = 2; // обнуляет число, на которое умножается p cout << "a. " << p << endl; while (p*i2 < max - 1) { // перебирает все кратные числу p for (int itoi2 = 0; itoi2 < filter.size(); ++itoi2) // проверяет, нет ли в фильтре полученного значения if (p*i2 == filter[itoi2]) // ++conc; if (conc<1) // если совпадения не обнаружено, добавляет число в фильтр filter.push_back(p*i2); conc = 0; ++i2; sort(filter.begin(), filter.end()); } ++p; for (int itop = 0; itop < filter.size(); ++itop) { if (p == filter[itop]) { ++p; itop = 0; } } } for (int i = 2; i<max-2 ; ++i) { //создает массив простых числел исключая составные fr = 0; for (int i3 = 0; i3 < filter.size();++i3) if (i == filter[i3]) ++fr; if (fr < 1) comp.push_back(i); } for (int out = 0; out < comp.size(); ++out) cout << out + 1 << ". " << comp[out] << ". " << endl; p = 2; filter.clear(); comp.clear(); } system("pause"); return 0; }Fox122
#include "stdio.h" #include "math.h" #include "iostream" using namespace std; int main() { setlocale(0, ""); int m, k = 0; cout << "Введите пределы!" << endl; cin >> m; int b = sqrt(m) + 1; int* simple = new int[m]; for (int i = 0;i < m;i++) simple[i] = i; for (int i = 0;i < m;i++) for (int j = 2;j < simple[i]; j++) if (simple[i] % j == 0) simple[i] = 0; for (int i = 0;i < m;i++) if (simple[i] > 1) { k++; cout << simple[i] << endl; } cout <<"количество простых чисел = " << k << endl; }}
raiden
#include <cstdio> // printf, scanf #include <cstddef> // std::size_t #include <cmath> // sqrt //#include <climits> // CHAR_BIT == 8 #include <vector> // vector :) typedef unsigned char ubyte; typedef std::vector< ubyte> arr_t; arr_t erath( std::size_t n ) { static const ubyte mask[8] = {1, 2, 4, 8, 16, 32, 64, 128}; std::size_t arr_size = 1 + ( n + 8)/8 ; arr_t ar(arr_size, 0x55);//because all even numbers are not prime, except 2 :) // 0 1 2 3 4 5 6 7 // 1 0 1 0 1 0 1 0 --> set 1 to i-th bit of arr , if i-is not prime number, set 0 - if i - is prime number. // for first element: // 0 1 2 3 4 5 6 7 // 1 1 0 0 1 0 1 0 ar[0] = 0x53; std::size_t n_sqrt = static_cast< std::size_t > ( std::sqrt(n+0.0)); for( std::size_t i = 3; i <= n_sqrt; i += 2 )// need to check only odd numbers { if ( !(ar[i>>3] & mask[i&7] ) ) // so i - is prime { for( std::size_t j = i * i , i2 =i + i; j <= n; j +=i2){ // i-odd, so i^2 - also odd, so step must be i*2 . ar[ j>>3] |=mask[j&7]; } } } return ar; } void print_primes( const arr_t& arr, std::size_t n ) { for( std::size_t i = 0; i <=n; ++i) if ( ! ( arr[i>>3] & (1<<(i&7))) ) std::printf("%d ", i); }Fox122
#include "stdio.h" #include "math.h" #include "iostream" using namespace std; int main() { setlocale(0, ""); int m, k = 0; cout << "Введите пределы!" << endl; cin >> m; int b = sqrt(m) + 1; int* simple = new int[m]; for (int i = 0;i < m;i++) simple[i] = i; for (int i = 0;i < m;i++) for (int j = 2;j < b; j++) if (simple[i] % j == 0 && j < simple[i]) simple[i] = 0; for (int i = 0;i < m;i++) if (simple[i] > 1) { k++; cout << simple[i] << endl; } cout <<"количество простых чисел = " << k << endl; }Кайл Брофловски
Простенько:
void erath(list<int>& lst) { auto it = lst.begin(); ++it; while (it != lst.end()) { lst.remove_if([it](int a){return ((!(a%(*it))) && a != (*it)); }); ++it; } }