More on primes

Yes, I’m still obsessed with prime numbers. I wrote a C program this time that can list or count prime numbers in a certain range, or do both. The C program is pretty fast, but in terms of large numbers, it takes a while to get the primes for large numbers.

I use something related to Euclid’s Algorithm for finding factors, except I turn things inside-out so that it avoids factors and finds primes. The program is quite short, about 60 or so lines, not counting comments. It was  a great way for me to freshen up my dusty C programming skills (I am recently more into Perl than anything).

The hardest part of writing this program seemed to be in getting it to accept numbers from the command line. This was because I needed to review all that about strings, pointers, casting, string conversion, and how argv[] and argc are structured.

Once it was written, however, I could use it to find primes in numbers that were nearly as big as I wanted. It couldn’t take scientific notation, which would be a bit more work to parse from the command line. I was happy with just using raw integers, even though many of them were on the order of 1012 and beyond.

One of the great advantages of having a small C program is that I could log on to several different UNIX machines (Linux mostly), and run an instance of the program on a different range of numbers. This was very helpful when the numbers were in the trillions, because I was aware I was on a timesharing system on each machine, and that looking for primes would push up the load average quite noticeably for lengths of time extending for as much as 3 hours, and having several processes on the same machine used in tandem by other users just wouldn’t do.

I used  the UNIX time command to find out how long my program takes to find primes in real time. It was intended for my own information, but I wished I had recorded the data, since if I ever find out about an improved algorithm, or make improvements myself, it would be nice to have times I can compare these to.

The largest numbers input were on the order of 1019, a number so big I needed to significantly reduce the range of numbers it searches in to 1000. To make a search of only 1000 integers, the program still took about 20 minutes for a range such as 5⋅1019 to 5⋅1019 + 1000. I found this law of diminishing returns quite unsatisfying. The higher the number the shorter the range you had to give it, unless you wanted the program to take forever.