Programming Praxis

I watch Stack Overflow and Reddit for questions about prime numbers. Most of the questions are basic, many are confused, a few are interesting, and some are just bizarre. A recent question falls in the latter category:

I need to make a list of the prime factors with multiplicity of all the numbers up to 300,001 that are equivalent to 1 modulo 4. My strategy is to make a list of the numbers 1 modulo 4, then calculate the factors of each. I don’t know how to calculate factors, but I know it’s complicated, so I figure somebody has already built a factoring program and put it on the web. Does anybody know a web API that I can call to determine the factors of a number?

For instance, if we limit the numbers to 50, the desired output is:

5	(5)
9	(3 3)
13	(13)
17	(17)
21	(3 7)
25	(5 5)
29	(29)
33	(3 11)
37	(37)
41	(41)
45	(3 3 5)
49	(7 7)

Calling a web API 75,000 times is a spectacularly wrong way to build the list, but I pointed the questioner to Wolfram|Alpha. Long-time readers of this blog know how to solve the problem directly, which we will do in today’s exercise.

Your task is to write a program to factor all the numbers up to 300,001 that are equivalent to 1 modulo 4. 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.

Pages: 1 2