A Modular Counter Algorithm for the Detection of the Prime Numbers

[BarisAlbayrakIEEE]

Primes by Modular Counters

Given a number N, find all prime numbers up to N (inclusive) using a counter based approach which finds the primes in the order of 10^7.
The method is less efficient than the sieve algorithms but introduces an approach similar to the Incremental Sieve of Eratosthenes.

Approach
Starting from 5 and incrementing by 2, inspect all numbers for being a prime.
Starts by creating two arrays:

• An array to store the prime numbers
• An array to store a counter for each prime number

While inspecting the numbers starting from 5 and increasing by 2, each counter is incremented by 1.
When a counter reaches the corresponding prime number, the counter is reset to 0 and the current number is known to be a composite.

Initially we have 2 and 3 as the prime numbers and the corresponding counters are 1 and 0.
Keep in mind that the algorithm semantically excludes 2.
We can consider that the two arrays initially contain 3 and 0 respectively.
Hence, initially:

• current counter array: { 0 }
• current prime array: { 3 } // 2 is excluded for convenience

Then, in each cycle of the inspection loop, all the values in the counter array are incremented by 1.
To illustrate, the 1st 3 cycles of the loop:

• Cycle 1: number = 5
  current prime array: { 3 }
  current counter array: { 1 }
  -> no values in the counter array reached the corresponding prime value
  -> 5 is a prime
  update prime array: { 3, 5 } // 5 is added
  update counter array: { 1, 0 } // counter 0 is added for 5
• Cycle 2: number = 7
  current prime array: { 3, 5 }
  current counter array: { 2, 1 }
  -> no values in the counter array reached the corresponding prime value
  -> 7 is a prime
  update prime array: { 3, 5, 7 } // 7 is added
  update counter array: { 2, 1, 0 } // counter 0 is added for 7
• Cycle 3: number = 9
  current prime array: { 3, 5, 7 }
  current counter array: { 3, 2, 1 }
  -> the 1st value in the counter array reached the corresponding prime value
  -> 9 is not a prime
  update counter array: { 0, 2, 1 } // counter is reset to 0 for 3
  prime array remains the same

See the documentation of primes_by_counters.hpp for more details.