Question

Дается натуральное число N. Создайте программу, которая отображает простые числа от 1 до N.C++

Answer 1

Відповідь:

#include <iostream>

#include <vector>

using namespace std;

void printPrimes(int n) {

   // Создаем массив boolean значений

   vector<bool> isPrime(n + 1, true);

   // Начиная с числа 2, проверяем каждое число в массиве

   for (int i = 2; i * i <= n; i++) {

       // Если число i простое, помечаем как не простое все числа, кратные i

       if (isPrime[i]) {

           for (int j = i * i; j <= n; j += i) {

               isPrime[j] = false;

           }

       }

   }

   // Выводим все элементы массива, которые остались простыми (true)

   for (int i = 2; i <= n; i++) {

       if (isPrime[i]) {

           cout << i << " ";

       }

   }

}

int main() {

   int n;

   cout << "Введите натуральное число N: ";

   cin >> n;

   cout << "Простые числа от 1 до " << n << ":" << endl;

   printPrimes(n);

   return 0;

}