Написать код в с++ (Вывести на экран n простых чисел)

1. Лобовой алгоритм

Пока мы не набрали n обычных чисел, будем перебирать числа от 2 до ... и пробовать разложить их на множители.

Код вложен в ответ.

2. Решето Эратосфена

Решето Эратосфена дозволяет быстро находить все обыкновенные числа на отрезке (в нашем случае x - какая-то константа).

Алгоритм

Пусть x равен 25.

Тогда мысль такая: запишем все числа от 2 до 25.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

По умолчанию все числа помечены как обыкновенные. Непосредственно тут числа, помеченные как составные, будут показываться в нижних индексах:

Берем 1-ое число 2. Оно помечено как обычное. От квадрата этого числа до x помечаем все числа, делящиеся на 2, как составные:

2 3 5 7 9 11 13 15 17 19 21 23 25

Берем последующее число, помеченное как обычное. Это 3. От квадрата этого числа до x помечаем все числа, делящиеся на 3, как составные:

2 3 5 7 11 13 17 19 23 25

Следующее обычное число - 5. От квадрата 5 до x помечаем все числа, кратные 5, как составные:

2 3 5 7 11 13 17 19 23

Квадрат всех других обычных чисел больше x. Решето построено.

Код

Перевернем массив, представляющий решето. В composite[i] хранится true, если i - составное, false по другому.

include lt;bits/stdc++.hgt;

using namespace std;

const int x = 2000000;

bool composite[x + 1];

void calc()

 for (long long i = 2; i lt;= x; ++i)

   if (!composite[i] amp;amp; (i * i lt;= x))

     for (long long j = i * i; j lt;= x; j += i)

       composite[j] = true;

int main()

   calc();

   int n;

   cin gt;gt; n;

   int k = 0;

   for (int i = 2; i lt;= x amp;amp; k lt; n; ++i)

     if (!composite[i])

         cout lt;lt; i lt;lt; " ";

         ++k;

   cout lt;lt; endl;

   return 0;