# Need a faster way to determine prime numbers than my algorithm

The problem I am solving is: "What is the largest prime factor of the number 600851475143?" The first step I took is to determine the highest value number I should be looking at as a possibility (600851475143 / 2). Next I wanted to check each prime number as I go to see if it is a factor of 600851475143. If so, I store it in a variable denoting the highest prime factor encountered so far.

On running the program the prime factor '6857' is the last output I am seeing for several minutes in my output. I entered this as the answer and it was correct. My problem is finding a way to streamline the algorithm to greatly reduce the processing time.

public class Euler3 {

public static void main(String[] args) {
long max = 600851475143L / 2;
long lgstPrime = 1;
boolean isPrime = true;

for (int i=2; i<max; i++){
for (int j=2; j<=i; j++){
if ((i % j == 0) && (j != i))
isPrime = false;
}

if ((isPrime) && (600851475143L % i == 0))
lgstPrime = i;

isPrime = true;     //reset
}

System.out.println("\n" + "the largest prime factor of the number 600851475143 is " + lgstPrime);
}

}

-
Use sieve of eratosthenes to find the primes then go through all the primes from largest down to find the largest factor. –  Loki Astari Jan 10 at 19:07
@LokiAstari That wouldn't be a good approach at the OP's level. The question is clearly a homework or quiz at an introductory level to loop programming, so the question is neither about primes nor algorithms. It's possible that the OP doesn't even know how to use arrays yet. –  Hosam Aly Jan 10 at 19:22
the OP does know how to use arrays, and this isn't a hw assignment, it's from Project Euler's site. I'm just practicing some problems there. –  gjw80 Jan 10 at 20:17
Learning about and/or deriving algorithms like the sieve, rather than brute-forcing an answer, is one of the primary purposes of Project Euler. This is a great example of it working right :) –  Bobson Jan 10 at 21:58
Be careful that the upper bound you have to test is not n/2 but sqrt(n) –  mariosangiorgio Jan 11 at 7:59

My problem is finding a way to streamline the algorithm to greatly reduce the processing time.

Well, if we take into account that we are on codereview, than an answer to this could be a little bit off the scope, as @HosamAly has already written, too. I will investigate this a little bit further.

Problems related to prime numbers are studied very extensive. The conclusion of this is, whatever you do, you will most probably just reinvent the wheel.

So the question should not be "how to reduce the processing time", it should be "how to handle my problem" which leads to the question of the problem definition. If your problem definition is just as mentioned "What is the largest prime factor of the number 600851475143?", then take the number, put it into Wolfram Alpha, and be done in 5 seconds.

If your problem definition is more like "How can I calculate the largest prime factor of a given integer?" Then find any algorithm/library, check if it is suitable and be done.

If your problem definition is a real world requirement, then find out the time constraint. It is always about time constraints for real world problems like this. Without a time constraint, you could improve it literally forever.

If your problem definition is more like "I want to improve my knowledge about coding and optimization in Java and I will try the problem xyz" Then there is no real answer to this. You could ask probably for some solutions on stackoverflow (as far as I got it, they do not like questions for euler problems there, so hide it a little bit. I would post an answer there if you link it).

long lgstPrime = 1;

Please write the full name, so everyone can read and understand it. Is it longestPrime, largestPrime, logarithmstPrime? You do not save real time or space by saving some characters (assuming we are in Java and not something like fortran77)

long max = 600851475143L;
for (int i = 2; i < max; i++) {
...
}

I do not think that your code will work and output anything. This is an infinite loop. Why? Because i is integer, integer will overflow at Integer.MAX_VALUE (2^31 - 1 or 2147483647) starting at Integer.MIN_VALUE or -2147483648 again. This will never reach max which is greater than 2147483647. So the loop will run forever.
Example to test:

final long max = 600851475143L;
for (int i = 0; i < max; i++) {
if (i == Integer.MAX_VALUE)
System.out.println("will overflow now");
}

Better:

long max = 600851475143L;
for (long i = 2; i < max; i++) {
...
}

For readability, stick to one coding style:

for (int i=2; i<max; i++){
for (int j=2; j<=i; j++){
if ((i % j == 0) && (j != i))

better:

for (int i = 2; i < max; i++) {
for (int j = 2; j <= i; j++) {
if ((i % j == 0) && (j != i))
-
"Because i is integer, integer will overflow at Integer.MAX_VALUE (2^31 - 1 or 2147483647) starting at Integer.MIN_VALUE or -2147483648 again. This will never reach max which is greater than 2147483647. So the loop will run forever." This explains why the program never completes then... –  gjw80 Jan 11 at 14:52
I have come to a much better version based on several people's tips in this thread. Thanks for the assistance. –  gjw80 Jan 11 at 20:30

You can use other techniques to find primes sieve of Eratosthenes:
But since this is a code review I will review the code you have:

The easiest optimization is to record primes as you go.
A number is prime if it is not divisible by any of the primes you have already found. Thus you don't need to check a number against all smaller numbers just all smaller primes.

public class Euler3 {

public static void main(String[] args)
{
long max = 600851475143L / 2;
long lgstPrime = 1;
boolean isPrime = true;

// I use ArrayList solely because I am too lazy to think of a better
// dynamically expanding array structure. You may find that other
// structures are better this is solely to demonstrate the algorithmic
// change that can be done in the code.
ArrayList<long>  primes = new ArrayList<long>();;

// start at 5 ( we have added 2/3 and know 4 is not prime).
// You should make this the same type as your max
// Just in case sombody changes the value of max to something much bigger
// without looking at the code.

// We know that all even number are not prime.
// So we can increment this loop by 2 each time.

// With quick maths you see that multiples of 3 will hit multiples of 2 on even
// multiples but not on add. So if you do increments of 2 followed by 4
// then you will skip all the multiples of 2 and 3 thus removing a lot of numbers

long inc = 2;
for (long i=5; i<max; i += inc, inc = 6 - inc)
{

// Move this to the top of the loop
// This makes the code eaaser to write.
// As you show we are assuming prime and then checking
// for failure.
isPrime = true;     //reset

// Inner loop just loop over the primes:
for (long j=0;j < primes.size(); ++j)
{
if (i % primes.get(j) == 0)
{
isPrime = false;
break;          // As soon as you find the number is not prime
}                   // break out of the loop.
}

if (isPrime)
{
if (600851475143L % i == 0)
{
lgstPrime = i;
}
}
}
}

}
-
As a general note, this code may suffer from severe performance problems, due to the unnecessary boxing. Since the number of prime numbers within the question's range is about 78,000 (primes.utm.edu/howmany.shtml), it could be better to use an integer array with an initial capacity of 80,000. This would lead to a much better performance. –  Hosam Aly Jan 10 at 19:35
You can eliminate the isPrime variable for a micro-optimization. Looping through the primes collection backwards is a bit faster, reducing primes.size() to one invocation for the inner loop. –  Dave Jarvis Jan 10 at 20:32
get() returns an int, I would need a long if it's an ArrayList<Long>. –  gjw80 Jan 10 at 21:06
@gjw80: get() should return the type store in the array. In this case Long. –  Loki Astari Jan 10 at 21:28

Your approach is naturally very slow. Let's calculate it together:

• For each number i between 2 and max, check whether it is prime.
• If i is prime, check whether it is a factor of your large number.

For i=10, you're doing 10 checks in the first loop. For i=100, you're doing a 100 checks. For i=1000, you're doing a 1000 checks. How many are these? This is called an Arithmetic Progression. When you've reached i=1000, you've made 1000*1001/2 = 500500 checks. At i=6857, you've made 23 million checks, and so on. Clearly you're not being efficient.

For the purposes of code review, think about the following optimizations:

• Why do you need to check whether i is prime? Think about it. Wouldn't it be faster to check whether (600851475143L % i == 0) directly? How many checks would your code perform if you use this approach, compared to your previous approach?

• In your inner loop, why do you need the condition j != i? Could you remove that, and suffice with j < i in the loop condition?

• When checking that whether a number is prime, do you need to check all the smaller numbers, or could it suffice to check a subset of them? To check whether 1009 is prime, do you need to divide it by 1008 or even 1000? Do you need to divide it by 700? Is there a smaller value where you can stop, and say confidently that this number is prime, because you checked all possibilities smaller than value?

• In addition to the previous point, can you think of a way to eliminate exactly half of all the values of j that you check?

-