Factoring integers for fun and profit

Sorry for the time between posts. I have been working on a project which has been monopolizing my time. Anyway we had a lull at work and there is a problem which crops up periodically which is I get a 3-5 digit number which I think might be prime. While my TI-89 will factor integer I also thought it would be relatively easy to write a program which is determines primality simply by searching for a divisor. Once a divisor greater than 1 and less than the number is found the number is composite.

Hence you simple use the mod operator in C to find a divisor and you only need to check integer less in the desired range if you do not find one then the number is prime. This program is a strait forward exersise I am thinking of giving to some of my programming tutoring students. Now I told one of the other tutors about this and they asked me if 2013 was prime, which I responded it was not. They asked me what its factorization was, which I did not know. They seemed upset, so challenge accepted. Next I was extending my program to provide the prime factorization of a number less than UINT_MAX which happens to be the same as ULONG_MAX. The result is this file.

The interesting thing is that trial division is highly inefficient method of doing prime factorization. However for integers up to 2^32-1 computers are fast enough for this method to give results in a reasonable amount of time. (1-2 secs) Now keep in mind that this is purely an interesting side project for me, as it has no practical use, i.e. code-breaking.

What was amazing was that when I went to ULLONG_MAX which is 2^64-1, this program broke. Not only is it too slow but the sheer size of integers causes segmentation faults. The first solution I thought of was using libpari to generate a list of primes. However libpari could only do this on a 64-bit native system, so the next step is to create a class which generates at its instantiation the list of primes from 2 to 2^64-1 (well 2^64-59 inclusive) This will require implementation of a decent prime sieve, since I have written Sieve of Eratosthenes before I am thinking that I will implement the Sieve of Atkin.

My hope is that this process will yield an algorithm that is O(n/log(n)) at detecting primes after the list has been generated. Doing this for arbitrary primes is a much harder question. <-massive understatement! If you have not done this and are interested in programming I highly suggest doing it once, its a wonderful afternoon of work.

Ed.  Do the back of the envelope calculation on how much memory you would need to hold all of the primes less than 2^64-1. Its a steep hill to climb.