Code_Class/prime.cpp at master · SI-Abid/Code_Class · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> prime;

    int n;
    cin >> n;

    bool stat[n + 5];

    // int sq = sqrt(n * 0.1) + 1;

    stat[0] = stat[1] = true;

    for (int i = 4; i <= n; i += 2)
    {
        stat[i] = true;
    }

    for (int i = 3; i * i <= n; i += 2)
    {
        if (!stat[i])
        {
            // prime.push_back(i);

            for (int j = i * i; j < n; j += i * 2)
            {
                stat[j] = true;
                // prime.push_back(j);
            }
        }
    }
    n==5;
    for (int i = 0; i <= n; i++)
        if(!stat[i]) prime.push_back(i);

        // if(stat[i]==false)
        //     prime.push_back(i);

    cout << prime.size() << endl;

    for (int p : prime)
    {
        cout << p << " ";
    }

    cout << endl;
    return 0;
}