4 ms·
Near 10M primes/second: Erdős-Selfridge categorization in C
- m_rn 1y agoImplementation of Erdős-Selfridge prime categorization achieving 8.68 million primes per second on standard hardware. Processes all primes from 2 to 15,485,863 (first million primes) in 0.1153 seconds. Algorithm optimizations: - 210-wheel factorization reduces trial divisions by 77% - Integer-only square root implementation - Hash table prime lookups with linear probing - Bit-packed category storage (4x memory reduction) - Memoization of recursive category computations Complexity: O(n log m) practical performance vs O(n√m) theoretical bound. Results match expected Erdős-Selfridge distributions across categories 1-10. Each prime categorization averages ~346 CPU cycles including factorization, hash lookups, and recursive computation. Code: https://gist.github.com/opsec-ee/bd829c3781bcfaace131628f8f4e6689 https://gist.github.com/opsec-ee/bd829c3781bcfaace131628f8f4... C11 compatible