cpp_concurrency/Programs/32_ParallelFor/PrimeNumbers01.cpp at master · pelocpp/cpp_concurrency · 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// ===========================================================================
// PrimeNumbers01.cpp
// ===========================================================================

#include "../Logger/Logger.h"
#include "../Logger/ScopedTimer.h"

#include "ParallelFor01.h"

#include <algorithm>
#include <cmath>
#include <execution>
#include <numeric>
#include <ranges>
#include <set>
#include <string>
#include <thread>
#include <unordered_map>
#include <vector>

namespace Globals
{
    // https://www.michael-holzapfel.de/themen/primzahlen/pz-anzahl.htm

    //static constexpr size_t UpperLimit{ 100 };             // Found:  25 prime numbers
    //static constexpr size_t UpperLimit{ 1000 };            // Found:  168 prime numbers
    //static constexpr size_t UpperLimit{ 100'000 };         // Found:  9.592 prime numbers
    //static constexpr size_t UpperLimit{ 1'000'000 };       // Found:  78.498 prime numbers
    //static constexpr size_t UpperLimit{ 10'000'000 };      // Found:  664.579 prime numbers
    //static constexpr size_t UpperLimit{ 100'000'000 };     // Found:  5.761.455 prime numbers

    //// 24 prime numbers
    //static constexpr std::size_t Start{ 1 };
    //static constexpr std::size_t End { Start + 100 };

    //// 6 prime numbers
    //static constexpr std::size_t Start { 100'000'001 };
    //static constexpr std::size_t End { Start + 100 };

    //// 4 prime numbers
    //static constexpr std::size_t Start { 1000000000001 };
    //static constexpr std::size_t End { Start + 100 };

    //// 3614 prime numbers
    //static constexpr std::size_t Start { 1'000'000'000'001 };
    //static constexpr std::size_t End { Start + 100'000 };

    //// 4 prime numbers
    //static constexpr std::size_t Start { 1'000'000'000'000'000'001 };
    //static constexpr std::size_t End { Start + 100 };

    //// 241 prime numbers
    //static constexpr std::size_t Start { 1'000'000'000'000'000'001 };
    //static constexpr std::size_t End { Start + 10'000 };

    // 114 prime numbers
    static constexpr std::size_t Start{ 1'000'000'000'000'000'001 };
    static constexpr std::size_t End{ Start + 5'000 };
}

// ===========================================================================

static bool isPrime(std::size_t number)
{
    if (number <= 2) {
        return number == 2;
    }

    if (number % 2 == 0) {
        return false;
    }

    // check odd divisors from 3 to the square root of the number
    std::size_t end{ static_cast<std::size_t>(std::ceil(std::sqrt(number))) };
    for (std::size_t i{ 3 }; i <= end; i += 2) {

        if (number % i == 0) {
            return false;  // number not prime
        }
    }

    return true; // found prime number
}

// ===========================================================================

static void test_parallel_for()
{
    std::size_t from{ Globals::Start };
    std::size_t to{ Globals::End };

    std::mutex tids_mutex;
    std::mutex primes_mutex;

    std::set<std::thread::id> tids;
    std::vector<std::size_t> primes;

    auto checkPrime = [&](std::size_t i) {

        std::thread::id tid{ std::this_thread::get_id() };

        {
            std::lock_guard tids_guard{ tids_mutex };
            tids.insert(tid);
        }

        if (isPrime(i)) {

            std::lock_guard primes_guard{ primes_mutex };
            primes.push_back(i);
        }
    };

    Logger::log(std::cout, "Start: ", from, " => ", to);

    {
        ScopedTimer watch{};

        Concurrency_ParallelFor::parallel_for_stl(
            from,
            to,
            checkPrime
        );

        //Concurrency_ParallelFor::parallel_for_ranges(
        //    from,
        //    to,
        //    checkPrime
        //);
    }

    Logger::log(std::cout, "Threads Used: ", tids.size());
    Logger::log(std::cout, "Found Primes: ", primes.size());
}

// ===========================================================================

void test_parallel_for_01()
{
    test_parallel_for();
}

// ===========================================================================
// End-of-File
// ===========================================================================