Optimize calculation of prime numbers

Question

I am trying Problem 3 from Project Euler and my algorithm is far too slow. Does anyone know how to optimize this? The number I am trying to calculate up to is 600851475143L. It takes forever to calculate this so I need a way to speed up the calculations.

LOGIC:

Go through all the numbers from 3 until that number-1
For each of these numbers check if they are prime by dividing them by all the numbers in between and if they dont divide by any of them then they are prime.

If prime then add them to an array.

public static void problem3(long number){

long number2 = number;
long sqrtNumber = (long)Math.sqrt(number2);


int indexNum = 1;
boolean isPrime = false;

int primeNums[] = new int[2];
primeNums[0] = 2;

//puts prime numbers into an array
for(int y = 3; y < sqrtNumber; y++){
   isPrime=true;
   for(int theNum = 2; theNum < y; theNum++){
       //if y divides evenly by any number then it is not prime         
       if(y%theNum==0){
           //dont store in array
           isPrime=false;
           break;
       }
   }

   if(isPrime == true){
       //add to array
       System.out.println(y);
       //put y in the array and exapnd the array
       //System.out.println("y: " + y);
       primeNums[indexNum] = y;

       int[] newArray = new int[primeNums.length + 1];
       System.arraycopy(primeNums, 0, newArray, 0, primeNums.length);

       primeNums = newArray;

       indexNum++;
   }
}

********** UPDATE **************

I calculated up to the square root which sped up the calculations a lot but I also done something else which was to add a break statement in the forloop to break once I discovered the number was not prime. I edited the code above to reflect these changes.

My algorithm is still wrong for calculating the prime factors though so I will need to have a look at it and maybe raise a new question.

You should implement the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) in order to solve the problem. — Luiggi Mendoza, Mar 27 '13 at 00:21
A simple factorisation by trial division would take a couple of milliseconds tops (less than 100 _microseconds_ here). — Daniel Fischer, Mar 27 '13 at 00:37
Please get rid of all the confusing `**edit**` annotations. Nobody cares about the errors you had, and the versioning is available for inspection for anybody who does. Your code is presently unreadable. — user207421, Mar 27 '13 at 05:38
the problem 3 from Project Euler does not ask you for all primes below 600851475143, neither for a biggest prime below 600851475143. It asks you for a biggest prime factor of 600851475143, i.e. such number `d` that `600851475143 % d == 0`. [Google Search for problem 3 on StackOverflow shows 7460 hits](http://www.google.com/search?q=problem+3+from+Project+Euler#hl=en&safe=off&sclient=psy-ab&q=problem+3+Project+Euler+site:stackoverflow.com). — Will Ness, Mar 27 '13 at 14:48
By the way, I was just looking at your code - are you really rebuilding your entire array of primes every time you find a new prime? That is grossly inefficient. At the very least, start with a large number an double it every time you get a new one. — atw13, Mar 28 '13 at 01:31

score 6 · Accepted Answer · answered Mar 27 '13 at 00:22

6

You don't have to divide by every number. You only have to divide by each prime number between 2 and the square root of your number.

answered Mar 27 '13 at 00:22

atw13

719
3
7

I think I seen that somewhere else. But why only divide each prime number up to the **square root**? – Phil Hunter Mar 27 '13 at 00:24
7

Because for every prime p by which x is divisible, x is divisible by x/p. If p > sqrt(x), then x/p < sqrt(x). – raptortech97 Mar 27 '13 at 00:26
1

Well, you only have to go to the square root because if some number less than the square root divides your number, then the quotient of those two has to be greater than the square root. For example, take the number 36. 18 divides 36, but you don't have to test 18 because you already tested 2. The highest number you need to test is 6. As for why just primes? If 4 divides a number, 2 must divide it. So you've already eliminated 4 as a factor if you've eliminated 2. – atw13 Mar 27 '13 at 00:27
1

Im sorry, that went totally over my head, but ill take your word for it and make the changes. :) – Phil Hunter Mar 27 '13 at 00:27
2

Let me try another example. Say you want to know if 67 is prime. The square root of 63 is a little above 8. So you test 2. Nope. Test 3. Nope. Skip 4, why? Because if it's not divisible by 2, it ain't divisible by 4. Test 5 - nope. Skip 6, same reason. Test 7 - nope. Test 8 - nope. Now we can stop. It can't be divisible by 9 because 9*8 is greater than 67, and we've eliminated any chance of 67 being equal to 9*2, 9*3, 9*4, 9*5, 9*6, and 9*7, since we tested (or skipped) all those numbers. – atw13 Mar 27 '13 at 00:32
Ok, I think I understand now, thanks. Im running my program now so if it works I will mark you up.. – Phil Hunter Mar 27 '13 at 00:37

score 4 · Answer 2 · answered Mar 27 '13 at 00:22

4

The first thing you can do is only test possible factors up through the square root of the number that you're testing, because if you find a factor greater than the square root, then you should have found a factor less than the square root.

If you need additional performance, then use the Sieve of Eratosthenes. That allows you to use the results of previous primes to cut down the work on determining if larger numbers are prime.

answered Mar 27 '13 at 00:22

rgettman

176,041
30
275
357

1

I think I seen that somewhere else. But why only divide each prime number up to the **square root**? – Phil Hunter Mar 27 '13 at 00:24
2

Consider [253](http://xkcd.com/247/), which is 11 * 23. The square root is approximately 15.9. If you found 23 (greater than the square root), then you should have found 11 (less than the square root) already. If you don't find a factor less than or equal to the square root, then you won't find one greater than the square root either. – rgettman Mar 27 '13 at 00:26
@PhilHunter since you want only prime factors, the bigger non prime factor would be the square root of the number. As a sample, `sqrt(100) = 10`. – Luiggi Mendoza Mar 27 '13 at 00:26
1

there's no need for the sieve of Eratosthenes here, because there's no need to test any numbers for primality. A proper trial division factorization (like e.g. here http://stackoverflow.com/a/12046123/849891 ) produces factors which are prime by construction. – Will Ness Mar 27 '13 at 20:03

Optimize calculation of prime numbers

2 Answers2

Linked