Original Prime Number Generator
Latest Prime Found:
487
All Primes Found:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487
How it Works:
While musing one day about a possible game in which enemies come in waves, with the type of enemy being determined by the prime factors of the wave number, I stumbled onto the idea that there were two ways I could increase an integer by manipulating its prime factors:
- Upgrade: I could increase the largest prime factor to the next-greater prime number.
- Expand: I could duplicate the largest prime factor.
In fact, as I thought about it more, every integer > 2 could be mapped uniquely to a smaller integer by these two operations. Every integer with a duplicated largest-factor is the result of an expansion, while every integer without a duplicated largest-factor is the result of an upgrade. And the only way to get a prime number is to "upgrade" the previous prime number.
Therefore, by counting up to a number, I would always determine whether it was composite by "upgrading" and "expanding" every smaller composite, and "expanding" every smaller prime. By elimination, if the number I counted up to wasn't composite, it must be a prime itself.
So, is this algorithm useful?
Prime numbers are not merely a fun curiosity. Determining the prime factors of an integer is an important piece of the science of modern cryptography. Therefore, a lot of effort goes into algorithms that can efficiently determine the prime numbers.
The modern industrial method for determining primes is called the Sieve of Atkin. I have no delusions that my algorithm can compete with the Sieve of Atkin at the things that the Sieve of Atkin does best. I have run benchmarks and found that the Sieve is many times faster, which makes sense since my algorithm, in order to determine whether odd number n is prime, must (on average) determine about n odd composite numbers.
(Running an optimized C++ version of my algorithm on my home laptop, it was able to determine the primes up to 111 million in 100 seconds. The bottleneck at that point was RAM, so that aspect could still possibly be optimized more.)
However, the Sieve works by first setting an upper bound on the primes to be found. If I use the Sieve to find the primes up to ten million, and then I decide I want to go to eleven million, I have to start over. My algorithm is different. By the time I have determined that 9,999,997 is prime or composite, I have already laid a lot of groundwork for numbers above ten million. Therefore, my algorithm might be more useful for unbounded cases, where I don't know in advance how high I want to determine prime numbers.
Optimized C++ Code:
#include <iostream>
#include <unordered_map>
#include <vector>
#include <chrono>
#include <cstdint>
class PrimeGenerator {
private:
std::unordered_map<uint64_t, uint64_t> prime_steps;
std::unordered_map<uint64_t, std::vector<uint64_t>> composites;
uint64_t prev_prime;
uint64_t count;
bool first_call;
public:
PrimeGenerator() : prev_prime(2), count(3), first_call(true) {}
uint64_t next_prime() {
if (first_call) {
first_call = false;
return 2;
}
while (true) {
auto it = composites.find(count);
if (it != composites.end()) {
// Current number is composite
std::vector<uint64_t> factors = std::move(it->second);
composites.erase(it); // Remove used composite
uint64_t last_factor = factors.back();
// Expansion: add another copy of largest factor
uint64_t expanded_prod = count * last_factor;
std::vector<uint64_t> expanded_factors = factors;
expanded_factors.push_back(last_factor);
// Upgrade: replace largest factor with next prime
uint64_t next_prime_val = prime_steps[last_factor];
uint64_t upgraded_prod = count * next_prime_val / last_factor;
std::vector<uint64_t> upgraded_factors = factors;
upgraded_factors.back() = next_prime_val;
composites[expanded_prod] = std::move(expanded_factors);
composites[upgraded_prod] = std::move(upgraded_factors);
} else {
// Current number is prime
composites[count * count] = {count, count};
prime_steps[prev_prime] = count;
prev_prime = count;
uint64_t result = count;
count += 2;
return result;
}
count += 2;
}
}
};
// Optimized version using more efficient data structures
class OptimizedPrimeGenerator {
private:
std::unordered_map<uint64_t, uint64_t> prime_steps;
std::unordered_map<uint64_t, std::vector<uint64_t>> composites;
uint64_t prev_prime;
uint64_t count;
bool first_call;
// Pre-allocate vectors to avoid frequent allocations
std::vector<uint64_t> temp_factors;
public:
OptimizedPrimeGenerator() : prev_prime(2), count(3), first_call(true) {
temp_factors.reserve(8); // Most factors lists are small
}
uint64_t next_prime() {
if (first_call) {
first_call = false;
return 2;
}
while (true) {
auto it = composites.find(count);
if (it != composites.end()) {
// Current number is composite - use move semantics
temp_factors = std::move(it->second);
composites.erase(it);
const uint64_t last_factor = temp_factors.back();
const uint64_t expanded_prod = count * last_factor;
const uint64_t next_prime_val = prime_steps[last_factor];
const uint64_t upgraded_prod = count * next_prime_val / last_factor;
// Expansion
temp_factors.push_back(last_factor);
composites[expanded_prod] = temp_factors;
// Upgrade - reuse the same vector
temp_factors.pop_back(); // Remove the added factor
temp_factors.back() = next_prime_val;
composites[upgraded_prod] = std::move(temp_factors);
temp_factors.clear(); // Prepare for next use
} else {
// Current number is prime
composites[count * count] = {count, count};
prime_steps[prev_prime] = count;
prev_prime = count;
const uint64_t result = count;
count += 2;
return result;
}
count += 2;
}
}
};
// Benchmark function template
template<typename Generator>
void benchmark_generator(const std::string& name, Generator& generator, int seconds) {
std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
std::chrono::high_resolution_clock::time_point end_time = start + std::chrono::seconds(seconds);
uint64_t count = 0;
uint64_t last_prime = 2;
while (std::chrono::high_resolution_clock::now() < end_time) {
last_prime = generator.next_prime();
count++;
}
std::cout << name << " in " << seconds << " seconds: "
<< count << " primes, last prime: " << last_prime << std::endl;
}
int main() {
std::cout << "C++ Prime Generator Benchmark
";
std::cout << "============================
";
// Test correctness first
std::cout << "First 20 primes:
";
OptimizedPrimeGenerator test_gen;
for (int i = 0; i < 20; i++) {
std::cout << test_gen.next_prime() << " ";
}
std::cout << "
";
// Benchmark both versions
PrimeGenerator basic_gen;
OptimizedPrimeGenerator opt_gen;
benchmark_generator("Basic C++ version", basic_gen, 10);
benchmark_generator("Optimized C++ version", opt_gen, 10);
// Full 60-second test with optimized version
std::cout << "
Full benchmark:
";
OptimizedPrimeGenerator full_gen;
benchmark_generator("Optimized C++ version", full_gen, 60);
return 0;
}
// Compilation instructions:
// g++ -O2 -std=c++11 prime_generator.cpp -o prime_generator
//
// Or with additional optimizations if compiler supports:
// g++ -O3 -march=native -std=c++14 -DNDEBUG prime_generator.cpp -o prime_generator