this post is sort of a continuation of my answer on the following question: Fast Algorithm to Factorize All Numbers Up to a Given Number. As this post explains – We need to factorize all the numbers up to a large N.
At first I gave a python solution which was pretty slow (since – you know, python), than I decided to write it in C++. I am not that good with C++ and I would like to have a code review about that answer:
#include <math.h>
#include <unistd.h>
#include <list>
#include <vector>
#include <ctime>
#include <thread>
#include <iostream>
#include <atomic>
#ifndef MAX
#define MAX 200000000
#define TIME 10
#endif
std::atomic<bool> exit_thread_flag{false};
void timer(int *i_ptr) {
for (int i = 1; !exit_thread_flag; i++) {
sleep(TIME);
if (exit_thread_flag) {
break;
}
std::cout << "i = " << *i_ptr << std::endl;
std::cout << "Time elapsed since start: "
<< i * TIME
<< " Seconds" << std::endl;
}
}
int main(int argc, char const *argv())
{
int i, upper_bound, j;
std::time_t start_time;
std::thread timer_thread;
std::vector< std::list< int > > factors;
std::cout << "Initiallizating" << std::endl;
start_time = std::time(nullptr);
timer_thread = std::thread(timer, &i);
factors.resize(MAX);
std::cout << "Initiallization took "
<< std::time(nullptr) - start_time
<< " Seconds" << std::endl;
std::cout << "Starting calculation" << std::endl;
start_time = std::time(nullptr);
upper_bound = sqrt(MAX) + 1;
for (i = 2; i < upper_bound; ++i)
{
if (factors(i).empty())
{
for (j = i * 2; j < MAX; j += i)
{
factors(j).push_back(i);
}
}
}
std::cout << "Calculation took "
<< std::time(nullptr) - start_time
<< " Seconds" << std::endl;
// Closing timer thread
exit_thread_flag = true;
std::cout << "Validating results" << std::endl;
for (i = 2; i < 20; ++i)
{
std::cout << i << ": ";
if (factors(i).empty()) {
std::cout << "Is prime";
} else {
for (int v : factors(i)) {
std::cout << v << ", ";
}
}
std::cout << std::endl;
}
timer_thread.join();
return 0;
}
I would especially like a review about my usage of threads (I am afraid it might slow down the code). The performance are reaching 6619 which is the 855th (out of 1662 primes up to 14140 ~ square root of 200000000) in 1.386111 hours, if you find any way to make it faster I will be amazing! A more semantic review is also very welcome (Like #include order?).
Just for fun and a point of reference if you are trying to run the code yourself:
Where X is time and Y is the prime reached (i). The orange tradeline is y = 13 * 1.00124982852632 ^ x. The graph is exponential since indeed the inner loop time is getting shorter.
The orange tradeline says I will reach 14107 (The highest prime before the square root) at x ≈ 5595.842803197861 seconds which is 1.554 hours!