sieve_experiment.py

'''
My teacher put a one liner for isprime on the board and we got into a brief discussion regarding efficiency. 
It is well known that the occurence of primes up to N is 1/log(N).

I've done qa sieve program before in my undergrad that was cool, but was not concered with efficiency. So I was
wondering if I could exploit a pattern that would allow one to quickly mark out primes.

I totally found one here!

Basically, I want to mark out non primes in a sieve, but ONLY ONCE. That is, 4's will not do anything, but 2's 
already took care of them.


So I went ahead and created a list of which mark numbers end up being the first to mark out a number in the sieve.


If you print it out, you will find a really cool pattern.

Obviously 2's will have all multiples of 2.

Looking closer, you will find the 2nd number of every marker ends up being the squared value!

as in 3 -> [3, 9, .....], 5 -> [5, 25, ....].


Looking even closer, I found that every other number started adding 2 times the value, while the others would cycle 
between adding 2 times and 4 times. I did not search for other patterns, but I want to know what is going on here.

Seems pretty legit.

'''

import sys

marks = [[i, []] for i in range(2, 1000)]
sieve = [[i, False] for i in range(2, 1000)]

for m in marks:
    for s in sieve:
        if s[1] == False:
            if s[0] % m[0] == 0:
                m[1].append(s[0])
                s[1] = True

for m in marks:
    sys.stdin.readline()
    sys.stdout.write('{}\n'.format(m))