## Two Sieving Problems

### August 27, 2013

We have today two exercises devoted to enumerating prime numbers:

1) How many prime numbers are there between 10

^{50}and 10^{50}+ 10^{6}?

2) How many prime numbers between 1,000,000 and 2,000,000 are congruent to 1 (mod 4)?

Your task is to write programs that answer the two questions given above; you might note the hint in the title of the exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

My first answers are in J; it’s definitely cheating when your language has a

“prime factors of” function.

Problem 1:

This takes a very long time to get anywhere; the second is much faster:

I originally had simpler answers, but decided that only working over odd

numbers (first question) or numbers equivalent to 1 mod 4 (second question) was

worth the uglification of my code.

My second answers are in Ruby; I can’t imagine trying to do these in a language

like C or C++, even with the help of multiprecision libraries like GMP or NTL.

I went with the Miller-Rabin primality test.

A Python version with segments.