Prime number generator exercise

Question

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
public class startListingPrimeNumbers {

    // method is created to start the prime number listing from 1 to infinity
    // and beyond
    public void startFromOneListingPrimeNumbers() {

        // 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;
        }
    }
}

Answer 1

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.

Answer 2

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:

   • Why not use Double or Float to represent currency?
   • Effective Java, 2nd Edition, Item 48: Avoid float and double if exact answers are required

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
   public class startListingPrimeNumbers {
   

   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.

   Source: The Java Language Specification, Java SE 7 Edition, 6.1 Declarations

   PrimeGenerator could be a good name for this class.

Answer 3

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);
        curPrimes.Add(2);
        curPrimes.Add(3);
        curPrimes.Add(5);
        curPrimes.Add(7);
        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)
                curPrimes.Add(k);
        }
        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...

Answer 4

@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.

Comments

@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...

Answer 5

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.

Answer 6

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 Eratosthenes¹ 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.

Answer 7

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.

For instance, instead of

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 +=.

Answer 8

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.

Answer 9

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;
}

Answer 10

Follow up on HungryBeagle's excellent answer:

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 :)