122COM_performance/pre_profiling.cpp at master · covcom/122COM_performance · 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
53
54
55
56
57
58
#include <vector>
using namespace std;

vector<int> find_first_n_version1( int n )
{
    vector<int> primes;
    primes.emplace_back(2);

    int counter = 3;
    while( primes.size() < n )
    {
        bool prime = true;

        for( int i=3; i<counter; ++i )
            if( counter % i == 0 )
                prime = false;

        if( prime )
            primes.emplace_back(counter);

        counter += 1;
    }

    return primes;
}

vector<int> find_first_n_version2( int n )
{
    vector<int> primes;

    int counter = 2;
    while( primes.size() < n )
    {
        bool prime = true;
        int half = counter/2;

        for( int i=0; prime && i<primes.size() && primes[i]<=half; ++i )
            if( counter % primes[i] == 0 )
                prime = false;

        if( prime )
            primes.emplace_back(counter);

        counter += 1;
    }

    return primes;
}

int main()
{
    int primesToFind = 1000;

    find_first_n_version1( primesToFind );
    find_first_n_version2( primesToFind );

    return 0;
}