9 replies to this topic

[TALucas]

Something that's held my attention for the past few years are prime numbers. I've been working on a java program that will efficiently search for large prime numbers, but this is no easy task. Let me list a few facts about primes before I get into my tutorial, and hopefully snag your interest too.

1...Prime numbers are only divisible by itsself and 1.
2...Interest in primes dates back to the time of ancient Egyptians.
3...There are many types of primes (Mersenne primes, Fermat primes, and twin primes) to name a few.
4...The largest prime found at the time of this tutoria has 12,978,189 digits. Ya, that's BIG!
5...Internet encryption is based off of factoring large primes.
6...The largest number I've proved prime is "10000000000000000000000013" and it took me 11 days. My latest most efficient version will cut that time by 75%.
7...There are some probabilistic algorithms that can determine to a very high degree weather a number is prime. These algorithms can test very large numbers very quickly, but what they can't do is determine their factors.
8...Most large primes found these days are by super computers or distributed computing.

OK, enough with that. The program I've included is a very simple version of my prime checker. This version is not very efficient, but is intended to demonstrate how to use the java BigInteger. The reason I've used the big integer is because the Java int is very limited in size when trying to find large primes. I've used the number "2147483648" because it is one larger than the upper limit for the "int". The BigInteger stores the number as a String, and therefore can be very large.

Check it out, and let me know if you have questions.

/*  Author:  TA Lucas
 *      Purpose: Will find the next prime number >= checkThisNumber
*/
import java.math.BigInteger;
public class Nextprime
{
 public static void main(String[]args)
 {
        BigInteger checkThisNumber = new BigInteger("2147483648");
  // This counts upwards until it reaches the next prime...
  // Includes the current number.
        while(!isPrime(checkThisNumber))
         checkThisNumber = checkThisNumber.add(new BigInteger("1"));
        // Prints the next prime number to the screen
        System.out.println(checkThisNumber.toString());
 }
 
 // This method tests whether a given number is prime or not.  It is not the most efficient
 // It does a couple checks to eliminate several numbers that cannot be prime.  For example,
 // it eliminates all even numbers except 'two'.  It also only check numbers that are
 // less than the square root of the number passed in....the upper limit is lowered each time
 // by the divisor.
   public static boolean isPrime ( BigInteger num )
   {
     boolean prime = true;
     BigInteger upperLimit = num;
     BigInteger divisor = new BigInteger("3");
  // Two is the only odd prime, so it returns true.
  if(num.compareTo(new BigInteger("2")) == 0)
  {
         prime = true;
    return prime;
  }
  // If any number is divisible by two it is not prime.  This eliminates
  // 50% of the numbers we have to check.
  if (num.mod(new BigInteger("2")).compareTo(new BigInteger("0")) == 0)
     {
         prime = false;
    return prime;
  }
     while(upperLimit.compareTo(divisor) >= 0 && prime)
     {
      // If there is no remainder it is not prime.
      if (num.mod(divisor).compareTo(new BigInteger("0")) == 0)
      {
          prime = false;
     break;
   }
   upperLimit = num.divide(divisor);
   // Adds 2 to skip even numbers.
   divisor = divisor.add(new BigInteger("2"));
     }
     return prime;
   }
}

[Alexander]

I like your interest in this, good work.

[Jarryd]

Quote

The largest number I've proved prime is "10000000000000000000000013" and it took me 11 days. My latest most efficient version will cut that time by 75%.

Thats very impressive, and interesting

[wim DC]

My laptop can find the first 30k primes in 1 min... Then I quit because it's always getting slower :P

[TALucas]

It really bogles my mind the size of these numbers. And when you are dealing with trillions of trillions of calculations, effeciency really comes into play. One unneeded repeated step could add days, weeks, months to the total calculating time. I understand that I don't have the resources to find the next largest prime...that would take teams of people and super computers, and lots of time. What I am doing, is working on a set of tools my (primes.java) that makes working with primes much easier. And I also hope to uncover some mysteries of the primes.


Checkout the prime here: 2^43112609-1 is prime and this is only part of the number. The entire number is stored in a 7MB text file.

[Generic]

Using constants for zero, one, two, and three could help your performance.

    public static final BigInteger TWO = new BigInteger("2");
    public static final BigInteger THREE = new BigInteger("3");

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 500; i++) {
            BigInteger checkThisNumber = new BigInteger("2147483648");
            // This counts upwards until it reaches the next prime...
            // Includes the current number.
            while (!isPrime(checkThisNumber)) {
                checkThisNumber = checkThisNumber.add(BigInteger.ONE);
            }
        }
        System.out.println("Finish Time: " + (System.currentTimeMillis() - startTime));
        // Prints the next prime number to the screen
        //System.out.println(checkThisNumber.toString());
    }

    // This method tests whether a given number is prime or not.  It is not the most efficient
    // It does a couple checks to eliminate several numbers that cannot be prime.  For example,
    // it eliminates all even numbers except 'two'.  It also only check numbers that are
    // less than the square root of the number passed in....the upper limit is lowered each time
    // by the divisor.
    public static boolean isPrime(BigInteger num) {
        boolean prime = true;
        BigInteger upperLimit = num;
        BigInteger divisor = THREE;
        // Two is the only odd prime, so it returns true.
        if (num.compareTo(TWO) == 0) {
            prime = true;
            return prime;
        }
        // If any number is divisible by two it is not prime.  This eliminates
        // 50% of the numbers we have to check.
        if (num.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
            prime = false;
            return prime;
        }
        while (upperLimit.compareTo(divisor) >= 0 && prime) {
            // If there is no remainder it is not prime.
            if (num.mod(divisor).compareTo(BigInteger.ZERO) == 0) {
                prime = false;
                break;
            }
            upperLimit = num.divide(divisor);
            // Adds 2 to skip even numbers.
            divisor = divisor.add(TWO);
        }
        return prime;
    }

output is around 1900 constantly.

while the code you posted is around 2800


You could also look into a mutable BigInteger

[TALucas]

Thanks for the code....I hadn't thought about that, and will implement in my other version. This version is not very efficient tho. It was just intended to show off the BigInteger.

[wim DC]

Also, you're checking if you can divide by 5, 15, 25, 35, 45,... while a simple check if the last digit of the number is a 0 or 5 will be enough to test all of the divisors that end in 5.

eg. A number that ends with 0 or 5 can never be prime, and by testing this you can ignore 1/5th of the divisors. Theoretically this results in a 20% speed increase.

Okay ugly while loop, can propably use an extra method, but it does what i explained.

[COLOR="red"][B]if(num.mod(FIVE).compareTo(BigInteger.ZERO) == 0){

            return false;

}[/B]

[/COLOR]

while (upperLimit.compareTo(divisor) >= 0 && prime) {

            // If there is no remainder it is not prime.

            if (num.mod(divisor).compareTo(BigInteger.ZERO) == 0) {

                prime = false;

                break;

            }

            // Adds 2 to skip even numbers.

            divisor = divisor.add([B][COLOR="red"]FOUR[/COLOR][/B]);


            if (num.mod(divisor).compareTo(BigInteger.ZERO) == 0) {

                prime = false;

                break;

            }

            divisor = divisor.add(TWO);


            if (num.mod(divisor).compareTo(BigInteger.ZERO) == 0) {

                prime = false;

                break;

            }

            divisor = divisor.add(TWO);


            if (num.mod(divisor).compareTo(BigInteger.ZERO) == 0) {

                prime = false;

                break;

            }

            upperLimit = num.divide(divisor);

            divisor = divisor.add(TWO);


        }

(Don't forget to only do upperLimit = num.divide(divisor); in the end of the while loop, and not just copy paste the original part of the while loop :P)
I went from ~3300 to ~1900. (starting from generic's code)

Edited by wim DC, 27 December 2010 - 02:36 AM.

[TALucas]

Quote

Also, you're checking if you can divide by 5, 15, 25, 35, 45,... while a simple check if the last digit of the number is a 0 or 5 will be enough to test all of the divisors that end in 5.

Ya....my other version does this. There is actually another little trick I figured out. The version I posted has this line:

divisor = divisor.add(new BigInteger("2"));

Basically that checks the number against every odd number. Let's say we are checking the number 13, the program would divide 13 by 3, then divide 13 by 5, then divide 13 by 7, etc. So basically it skips any even divisor, since even divisors are themselves divisible by 2....we don't need to make those checks. When you start at 3 and increment the divisor by two, it only checks the odd numbers.

1...2...[SIZE=5]3[/SIZE]...4...[SIZE=5]5[/SIZE]...6...[SIZE=5]7[/SIZE]...8...[SIZE=5]9[/SIZE]...10...[SIZE=5]11[/SIZE]...12...[SIZE=5]13[/SIZE]

The next logical step is to eliminate all divisors that themselves are divisible by 3. We've removed all even numbers (2,4,6,8,etc) and we need to remove all odd divisible by 3 (6,9,12,etc). So the only numbers that we check when we eliminate divisors divisible by 2 and 3 are list on the number line below.

So now, we can increment the divisor in the following pattern: From 1 to 5 we add 4, From 5 to 7 we add 2, and from 7 to eleven we add 4. From 11 to 13 we add 2, from 13 to 17 we add 4. From 17 to 19 we add 2 and from 19 to 23 we add 4. This pattern continues forever. I hope I'm not loosing you.

We increment the divisor by 4 then check for a prime,
We increment the divisor by 2 then check for a prime,
We increment the divisor by 4 then check for a prime,
We increment the divisor by 2 then check for a prime.

 1...2...3...4...[SIZE=5]5[/SIZE]...6...[SIZE=5]7[/SIZE]...8...9...10...[SIZE=5]11[/SIZE]...12...[SIZE=5]13[/SIZE]...14...[SIZE=2]15[/SIZE]...16...[SIZE=5]17[/SIZE]...18...[SIZE=5]19[/SIZE]

Hopefully not too bad so far. If we want to eliminate all numbers divisible by five (5, 10, 15, etc) the patter becomes:

Starting at 1 we increment 6,
Check for prime and increment 4,
Check for prime and increment 2,
Check for prime and increment 4,
Check for prime and increment 2,
Check for prime and increment 4,
Check for prime and increment 6,
Check for prime and increment 2.

 1...2...3...4...[SIZE=2]5[/SIZE]...6...[SIZE=5]7[/SIZE]...8...9...10...[SIZE=5]11[/SIZE]...12...[SIZE=5]13[/SIZE]...14...[SIZE=2]15[/SIZE]...16...[SIZE=5]17[/SIZE]...18...[SIZE=5]19[/SIZE]

...20...21...22...[SIZE=5]23[/SIZE]...24...25...26...27...28...[SIZE=5]29[/SIZE]...30...[SIZE=5]31[/SIZE]...32...33...34...35...36

Basically, we can keep going. We would next add 7, then 11, then 13 and so on to our list. Each time we add a number to our list, the patter increases in length exponentially.

In my optimized version of this program, I read in a list of primes that I use to create a pattern. I don't recall the exact number, but the pattern length in my program is in the hundreds of thousands.

[wim DC]

Kewl, i did the same (i think) when i wrote the code for listing all the primes.

I had an integer counting up per 2, and i would check if it's a prime or not by testing if it's divisable by the previous primes (excluding 1 and 2 ( even numbers were left out) ) up to the point where the divisor becomes bigger than half the number.

So if i would test 41 i would test the following only: 3,7,11,13,17,19 (which looks pretty much as the bigger numbers in your pattern)

I also think this is the fasted way (eg. The least numbers to check division) to be sure that it's a prime, but this requires a list of the numbers to check.
So this way is impossible to check 1 number unless, like you did, you have it stored in a file.

I don't think there is another way to optimize this.. Just make sure you use as least "new" keywords in the loop as possible.

Shouldn't the 3 stay big in the pattern?