Implementation 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.
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/bd829c3781bcfaace131628f8f4...
C11 compatible