# Prime number generator exercise

I have been trying to create a class that would list prime numbers forever. I know it has already been done but I think I learned some valuable principles during my trials.

This project helped me understand (to a better extent) return values, arguments for methods, simple math arithmetic and what I personally enjoyed working with was the power of the for and if/else statements.

I would appreciate any insight into improvements that would increase this code performance and/or any obvious flaws with my code structure.

//first the class is declared

// method is created to start the prime number listing from 1 to infinity
// and beyond

// Create the primary for loop using doubles so the program will
// continue on infinitely
for (double x = 1; x > 0.000; x = x + 1.000) {

// The double c is for determining numbers that only have 2 factors
// are prime
double c = 2.000;

// I use the primeLogger to keep track of each numbers amount of
// factors it contains, to later compare this value to c to know if
// it's prime or not
double primeLogger = 0.000;

// the multiplier is used to iterate through the for loop below
double multiplier;

// this is the bread and butter, I take multiplier and iterate it
// until it is greater than x, if a remainder exists from x divided
// by multiplier then my primeLogger adds nothing to itself
// if there is no remainder then primeLogger adds one, meaning
// multiplier is a factor of x.

for (multiplier = 1.000; multiplier <= (x); multiplier = multiplier + 1.000) {
if (x % multiplier == 0) {
primeLogger = primeLogger + 1.000;
} else {
primeLogger = primeLogger + 0.000;
}
}

// here we see if there are only 2 factors for x, and the console
// prints the number
if (c == primeLogger) {
System.out.println(x + " is a prime number");
}

// primeLogger is set back to zero to go on to the next x value
// based on the primary for loop description
primeLogger = 0.000;
}
}
}

• I never programmed in Java, but when I did it in C, I used an Int64. Is there a reason to use a double here? – Canadian Luke Mar 7 '14 at 17:53

The major problem here is using imprecise floating point values. Not only does it slow the entire process (minor quibble), but it will produce incorrect results once the values pass the integral cutoff of the field width. If you truly want to allow calculations approaching infinity (or what? 24 bits?) you need to switch to BigInteger which can model "exact" integers of any size.

Okay, they probably cap out at a very, very large number...much larger than doubles, but will likely last past the life of your PC.

This issue is so critical to the correctness of the solution that I'll leave it to stand on its own and leave any other review issues for others.

1. +1 to @David Harkness and here is an example:

final double original = 123456789123456789.0;
double d = original;
d = d + 1.000; // or d++
System.out.println(d == original); // true
System.out.printf("%f%n", original); // 123456789123456784,000000
System.out.printf("%f%n", d);        // 123456789123456784,000000


And two references:

2. if (x % multiplier == 0) {
primeLogger = primeLogger + 1.000;
} else {
primeLogger = primeLogger + 0.000;
}


The else branch seems superfluous, I guess you could remove it:

if (x % multiplier == 0) {
primeLogger = primeLogger + 1.000;
}

3. //first the class is declared


Later you'll find that comments like this one are just noise. It says nothing more than the code already does, it's obvious from the code itself that it's a class declaration, so I'd remove it. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

4. double multiplier;
...
for (multiplier = 1.000; multiplier <= (x); multiplier = multiplier + 1.000) {


The multiplier could be declared in the for loop.

for (double multiplier = 1.000; multiplier <= (x); multiplier = multiplier + 1.000) {


(Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

5. Class names should be nouns, instead of verbs and the first letter should be uppercase:

Class and Interface Type Names

Names of class types should be descriptive nouns or noun phrases, not overly long, in mixed case with the first letter of each word capitalized.

PrimeGenerator could be a good name for this class.

• I think this can be illustrated even cleaner with System.out.println(123456789123456789.0) and watch it print ...784.0. – corsiKa Mar 7 '14 at 19:17

I did a similar project myself, and there's a few rules you can use (one of which was already mentioned by @orion:

1. A number will never have a prime factor > FLOOR( SQRT( number ))
2. After 2, no even number is prime.
3. After 5, no number ending in 5 is prime.
4. Since the primes are factors of larger #'s, you can save the primes, and iterate over the array of primes to test if a number is prime.

Here's what I ended up using:

static void Main(string[] args)
{
long sqrtFloor;
List<long> curPrimes = new List<long>(100000000);
bool found;
int j;
System.Diagnostics.Debug.Print("Start Time=" + DateTime.Now.ToString());
for (long k = 11; k < 1000000000; k += 2)
{
if (k % 10 == 5)
continue;

found = false;

sqrtFloor = (long)Math.Floor(Math.Sqrt(k));

j = 0;
while (curPrimes[j] < sqrtFloor && found == false)
{
if (k % curPrimes[j] == 0)
found = true;
++j;
}

if (!found)
}
System.Diagnostics.Debug.Print("End Time=" + DateTime.Now.ToString());
found = true;
}


As I'm sure someone else has pointed out, there's no way even a double could go on forever printing out primes, as it would eventually overflow the mantissa, so it's irrelevant that my example only goes to 1,000,000,000 - You could increase it, but you start running into how long it takes to run. I think it took a little over an hour on an i3 laptop for this, and it would increase by multitudes for each factor of 10. Anyways, using 128 bit numbers would be your best bet...

• why stop at skipping over every multiple of 2 and 5? And why did you choose 2 and 5, but not 3? I feel like at that point, you might as well take it to its logical conclusion, which is the sieve of eratosthenes – Red Alert Mar 8 '14 at 0:43
• Actually, until I read the other answers here, I wasn't aware of the sieve of eratosthenes. Overall, I think it's a really clever approach, but I did have concerns w/ the added storage; However, @Orion has an excellent example below w/ wheel factorization! – HungryBeagle Mar 10 '14 at 14:10

@DavidHarkness and @palacsint warned about the general mis-use of double, because of precision, but I wonder why would you even consider it when looking for prime numbers? Do you know any non-integer prime number?

Ok, so you say - I want it to be able to calculate really big numbers, and I was not aware of the cutoff. But why use double for c (the constant 2.000)? or for primeLogger? It makes the code less readable, since it implies non-integer numbers. Personally, I got dizzy from all the 1.000000 in a prime number algorithm - 1.0 is more than enough...

Some other issues:

Infinite for loops -

for (double x = 1; x > 0.000; x = x + 1.000) {


very cumbersome and hard to read

for (double x = 1; ; x++) {


does exactly the same, easier on the eyes

Fail fast!

In your algorithm, you iterate over all the numbers smaller than x, count all its divisors, and then check if there are less than two of those.

This is a very inefficient algorithm - you should stop counting at two! Big numbers may have thousands of divisors, but you only need one to know they are not primes!

Even more so, you count 1 as a divisor. As I don't know of any prime who doesn't have 1 as a divisor, you can skip it, and look for any non 1 divisor to conclude the number is not a prime.

Redundant code

primeLogger = 0.000;


is totally redundant, as you declare it inside the block, and set it at the beginning of it. No need to 'reset' it.

@palacsint mentioned superfluous comments, I'd like to add that when there are more comments than code it is a big smell - your code should be descriptive enough for a reader to comprehend:

// I use the primeLogger to keep track of each numbers amount of
// factors it contains, to later compare this value to c to know if
// it's prime or not
double primeLogger = 0.000;


...this probably means the primeLogger is not a good name... how about numOfFactors? Less needed to explain...

You are testing many many more divisions that necessary. The number is always divisible by itself, and if it's not divisible by anything up to sqrt(x), it must be prime:

Like this:

for (multiplier = 2; multiplier*multiplier <= x; multiplier = multiplier + 1)


It's easier and cleaner to square left side than to root right side. Number 1 is a special case anyway. This does change counting the divisors a little bit. Every divisor above sqrt(x) has a symmetric pair below sqrt(x). Which means that your primeLogger should be multiplied by 2 at the end, and additionally subtract 1, if x was a perfect square (in that case you counted the middle one twice). However, this GREATLY reduces the number of trial divisions.

Additionally, if you are not factoring numbers, only finding primes, you can stop checking immediately after finding a factor. You don't even need primeLogger in that case.

If you are happy to excercise coding abilities as a hobby, you can have a lot of fun making an arbitrary-precision integer class from scratch (hold an array of unsigned integers and override casting, multiplication, addition and division operators to perform carry and other required operations).

Prime number generation is usually one of the first interesting things one does when learning programming. There are A LOT of optimizations that you can do without advanced math, but I won't bother you with that right now. Have fun.

• "the largest non-self divisor possible is sqrt(x)". This is not true; the correct statment is "If a non-self divisor larger than sqrt(x) exists then a divisor smaller than sqrt(x) also exists" – Taemyr Mar 7 '14 at 12:43
• Well yes that's what I meant. What remains after dividing out up to sqrt(x), what's left must be prime. So if you are checking primality, it doesn't matter but counting divisors may be wrong. Fixing. – orion Mar 7 '14 at 12:50

You've gotten a number of hints about how to speed up the code, but a few points seem to have been missed.

The first and biggest is that once you've determined that the number isn't divisible by 2, you've also determined that it can't possibly be a multiple of any other even number, so you can skip testing against any other even numbers.

if (x % 2 == 0)
return false;

for (long multiplier = 3; multiplier * multiplier <= number; multiplier += 2)
if (number % multiplier == 0)
return 0;


Although it departs from the nature of the code you posted, it's also worth considering using the sieve of Eratosthenes1 to generate the first several million primes or so. After you've generated the first primes that way, you can use the table of primes it produces in trial division to produce larger primes--instead of doing trial division by all odd numbers, you can do trial division only by the primes (from the table) up to the square root of the number being tested.

1. There are alternatives such as the sieve of Atkins, but they're quite a bit more difficult to code, and the sieve of Eratosthenes is already dramatically faster than trial division.

The others have pointed out many things, but I have one thing to add:

Instead of using the + operator for accumulating a total, thus having to write the left-hand operand twice, you can use the += operator instead.

number = number + 2;


you'll have

number += 2;


The relevant statements would look like this. I'll also apply some of @palacsint's suggestions so that you can see the improved code together.

for (double x = 1; x > 0.000; x += 1.000) {
// ...
for (double multiplier = 1.000; multiplier <= (x); multiplier += 1.000) {
// ...
primeLogger += 1.000;
// ...
}
}


Although those three variables should just be incremented by one with ++ (based on @Uri Agassi's advice), I've shown the use of += here just for demonstration. For values other than one (which only works with ++ or --), you would use +=.

To provide another view on the use of double to represent integer numbers. If you run the following code (ideone link) you will find that around 2^53 double will fail you. The reason is that double is a 64 bit floating point type with 53 bit mantissa which gives you around 16 significant decimal digits.

Test code:

    public static void main (String[] args) throws java.lang.Exception
{
long l = 1;
double d = 1.0;
for (int i = 0; i < 63; ++i)
{
l *= 2;
d *= 2.0;

System.out.format("     n: %d\n", i + 1);
System.out.format("  long: %d (+1 = %d)\n", l, l + 1);
System.out.format("double: %.0f (+1 = %.0f)\n", d, d + 1.0);
System.out.println();
}
}


At i = 52 the output is:

     n: 53
long: 9007199254740992 (+1 = 9007199254740993)
double: 9007199254740992 (+1 = 9007199254740992)


So all of a sudden x + 1 = x when using double because on floating point adding a small value to a very large value just results in the very same large value.

Conclusion: Using long would give you a larger range than double.

The biggest speedup, to agree with others, is that you don't have to brute force test every number. There are really only two things to keep in mind:

1. You need to test up to the square root of the number you're trying to prove is prime, since the square root of a number will be the center of its set of divisors (ie, any factors of a number will have one number less than the square root, and one number greater than the square root).

2. You only need to test the primes that are less than the square root of said number.

Example: Let's say the number you're trying to test is 37. First, you find the square root, which is slightly greater than 6. Then determine the primes <=6, which are 2, 3, and 5, and then divide 37 by these numbers.

Here's my own version to show you what I'm talking about. It'll only stop when you run out of memory ;) :

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int main(){
vector<long long> primes; //stores primes that have been found
long long totest = 5;
long long median = ceil(sqrt(totest));
long long count = 0;    //counts the number of tests on each number
bool running = true;
primes.push_back(2);
primes.push_back(3);
cout <<"Output takes the form prime, number of tests, size of prime database.\n";
cout << "2, 0, 1" << endl << "3, 0, 2" << endl;
while(running){
long np =-1;
for(long long index = 0; primes.at(index) <= median; index++){
np = totest % primes.at(index);
count++;    //so for every test, i increment the test counter
if(np == 0){ count = 0; break;}
}
if(np != 0){
primes.push_back(totest); //if none of the existing primes can divide the current number, add it to the list of primes to test for bigger primes.
cout << totest << ", " << count << ", " << primes.size() << endl;
}
totest++;
count = 0;
median = ceil(sqrt(totest));
}
return 0;
}


The generalization of excluding factors of 2 and 3 (and so on) from search is called Wheel factorization. In my opinion the best is to do it for 2,3 and 5. It has a period of 30 (relatively small), and exactly 8 jumps between prime candidates: (6,4,2,4,2,4,6,2). You see the appeal: only 8 candidates out of 30 are tested, and 8 is perfect for iteration (for binary reasons).

You output 2,3,5 as primes, then start jumping (testing 1+6,1+6+4,1+6+4+2,...). If you include 7 or higher you have a bigger jump table and less and less improvement. The formula is: number_of_jumps=number_of_candidates=phi(2*3*5*...)=(2-1)*(3-1)*(5-1)*..., where phi is Euler's Totient function. So for 2, your trade-off is 1/2, for 3 it's (1/2)*(2/3), for 5 it's (1/2)*(2/3)*(4/5)=8/30=26.7%, and for 7 it's (1/2)*(2/3)*(4/5)*(6/7)=48/210=22.8% which is slightly better, but requires BIGGER jump table, which also isn't of size 2^n. It's true, when you are doing primes sequentially from 2 up, you can use full sieve (remember all previous primes) but usually you need a test for a specific prime.

Here's quite a fast and short code in c:

#include <stdio.h>
#include <stdint.h>

int main(){
static const uint64_t jumptable[]={6,4,2,4,2,4,6,2};
printf("%ld\n%ld\n%ld\n",2,3,5);//output first three
uint64_t index=1;//for cycling through jumptable
for(uint64_t n=7;1;n+=jumptable[0x7&(index++)]){//infinite loop
//wheel test
int is_prime=1;
uint64_t index2=1;//inner wheel
for(uint64_t m=7;m*m<=n;m+=jumptable[0x7&(index2++)]){
if(n%m==0){is_prime=0;break;}
}
if(is_prime)printf("%ld\n",n);
}
return 0;
}


These are the basic improvements. After this step, you can employ advanced primality tests, such as Miller-Rabin test or Pollard's Rho test, which bring orders of magnitude of improvements. But this first step still eliminated a lot of unnecessary tests.

You can guess I've done this before :)