The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when for primes , the degree is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.[ref]
Use quotient arguments . There are distinct values: indices at most contribute that many, and larger indices yield values below . The floor function identity keeps later quotients in this table.
For each exponent , initialize . Process primes in increasing order, and eligible in decreasing order, applying
This removes composites whose smallest prime factor is . The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing ensures each smaller argument still has its pre- value. After sieving, is the desired sum of over primes up to .
To restore composites, let be the th prime and let sum over with every prime factor greater than . Set for . Otherwise its prime contribution is , and add
Unique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With , and , the answer is . No complete-multiplicativity assumption is needed.
For the Euler totient function up to six, the prime contribution is . The composites add , and gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.

Articles by others on the same topic (0)

There are currently no matching articles.