Челики, еще задачку дали, как делать, елы палы.

линейный Эратосфен делает бр-бр-бр:

 #include 

#include 

 



using namespace std;





int main() {

    int n;

    cin >> n;

    vector lp(n + 1, 0), p;

    for(int i = 2; i

Да, решето Эратосфена - нормальный по скорости вариант. Но классическое - без заморочек с отдельным массивом простых чисел - намного проще.

 #include  

#include  

#include  

 

using namespace std; 

 

int main() { 

    int n; 

    cin >> n; 

    vector t(n + 1, true); 

    for (int i = 2; i * i

Чтобы N (1≤N≤1000000) можно было вводить любое количество раз:
#include <vector>
#include <iostream>
using namespace std;
unsigned long a[31251], b[32], c[32];
void fal(unsigned long x)
{ a[x >> 5] &= c[x & 31]; }
unsigned bit(unsigned long x)
{ return a[x >> 5] & b[x & 31]; }
int main()
{ unsigned long i, j, k, l, m = 31251,
n = 1000000, N; vector <unsigned long> p;
i = 1; b[0] = i; c[0] = ~i; for (j = 1; j < 32; j++)
{ i <<= 1; b[j] = i; c[j] = ~i; } for (i = 0; i <= m; i++)
a[i] = 4294967295; fal(0); fal(1); i = 1000;
for (j = 2; j <= i; j++) if (bit(j)) { k = n / j; for (l = 2;
l <= k; l++) fal(l * j); } while (true) { cout << "N: ";
cin >> N; k = 0; if (N == 1) { cout << k << endl;
break; } if (N == 2) { cout << 1 << '\n' << 2 << endl;
break; } k = 1; p.push_back(2); for (i = 3; i <= N; i += 2)
if (bit(i)) { k++; p.push_back(i); } cout << k << endl;
for (i = 0; i < p.size(); i++) cout << p[i] << ' ';
cout << endl; p.clear(); } }Плохо только то, что все простые надо одной строкой выводить -так не очень красиво получается...

Перебор всех чисел от 1 до указанного. Проверить каждое; если оно простое, сохранить в массив, увеличить счётчик на 1. После перебора вывести количество простых чисел и элементы массива

#include <iostream>
#include <vector>
using namespace std;

int main(){
int n;
vector<int> res;
cin >> n;
for(int i = 2; i <= n; i++){
bool norm = true;
for(int j = 2; j * j <= i; j++)
if(i % j == 0)
norm = false;
if(norm)
res.push_back(i);
}
cout << res.size() << "\n";
for(int i = 0; i < res.size(); i++)
cout << res[i] << " ";
}