Implementation of a Parametric Sieve for Prime Number Generation

This repository contains the reference C++ implementation of the polynomial sieve with parameter-dependent threshold introduced by Tabalevich & Alexandrov (2025, DOI: 10.5281/zenodo.17563598). The sieve defines a condition S(p) that tests prime candidates p(a,b,d)=(n(a,b,d)+1)2−(b+2) against quadratic congruences modulo (4x+2) for x<c(a,b), where c(a,b)=a2+a+(a+1)b and n(a,b,d)=2a+b+2c(a,b)−2d. Key features: OpenMP parallelization for multi-core architectures (tested up to 12 threads) 128-bit integer arithmetic support (__int128) for exact computation up to A=5000 Deterministic Miller-Rabin primality test for 64-bit integers (conclusive for full tested range) Memory-efficient implementation with O(1) memory per thread Computational results: Verified for all parameter triples (a,b,d) with a≤3000 (9×106 candidates) Generated numbers up to 1.4×1013 No escaped composites (false positives) detected: ∣E(3000)∣=0 Observed prime density in sieved set QS(A): δ≈10.1% (A=3000), vs. natural density ≈3.4% for numbers of comparable magnitude Theoretical significance: The code supports verification of the central conjecture that the sieve S(p) is a deterministic primality test for the family {p(a,b,d)}. The implementation confirms the predicted asymptotic density consistent with the Bateman-Horn conjecture (CBH≈0.108). Dependencies: C++17 compiler, OpenMP library. Usage: ./sieve <A_max> <num_threads>. Example: ./sieve 3000 12. For complete mathematical analysis and proofs, see the research article in this repository.