Prime Number Clock.md

Prime Number Clock

This example streams the prime number sequence without using trial division.

We represent the integers as a clock and assign each prime number a hand on the clock.

The 2 hand rotates the clock every other cycle, the 3 every third cycle, the 5 hits midnight every fifth cycle, and so forth.

Here are the states of the clock for the first 16 integers:

1

Hands     |
Positions |

2

Hands     | 2
Positions | 0

3

Hands     | 2 3
Positions | 1 0

4

Hands     | 2 3
Positions | 0 1

5

Hands     | 2 3 5
Positions | 1 2 0

6

Hands     | 2 3 5
Positions | 0 0 1

7

Hands     | 2 3 5 7
Positions | 1 1 2 0

8

Hands     | 2 3 5 7
Positions | 0 2 3 1

9

Hands     | 2 3 5 7
Positions | 1 0 4 2

10

Hands     | 2 3 5 7
Positions | 0 1 0 3

11

Hands     | 2 3 5 7 11
Positions | 1 2 1 4  0

12

Hands     | 2 3 5 7 11
Positions | 0 0 2 5  1

13

Hands     | 2 3 5 7 11 13
Positions | 1 1 3 6  2  0

14

Hands     | 2 3 5 7 11 13
Positions | 0 2 4 0  3  1

15

Hands     | 2 3 5 7 11 13
Positions | 1 0 0 1  4  2

16

Hands     | 2 3 5 7 11 13
Positions | 0 1 1 2  5  3

Hint

Watch a single hand move and observe the pattern. Take the 3 hand for instance:

0
1
2
0
1
2
0
1
2

primes.cpp

/*
 * Print out prime numbers sequentially
 *
 * Compile with
 *     c++ -std=c++11 primes.cpp
 */

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int32_t hands = 1;
    vector<int64_t> clock  { 0 };
    vector<int64_t> primes { 2 };

    for (int64_t i = 3; ; i++) {
        bool is_prime = true;
        for (int32_t hand = 0; hand < hands; hand++) {
            clock[hand]++;
            if (clock[hand] == primes[hand]) {
                clock[hand] = 0;
                is_prime = false;
            }
        }
        if (is_prime) {
            clock.push_back(0);
            primes.push_back(i);
            hands++;
            cout << i << endl;
        }
    }

    return 0;
}