# Thread: Making this program more efficient

1. Member Join Date
Jan 2015
Location
Miami, FL
Posts
86
Rep Power
0

## Making this program more efficient

This program works perfectly and I know it can generate the correct answer but it's too slow.

This is problem number 3 from Project Euler and the question is What is the largest prime factor of the number 600851475143(Try it yourself and you'll see how long it takes)?

The example they give is that the largest prime factors of 13195 is 5, 7, 13 and 29. This means that 29 is the largest prime factor for that number which is what I get.

The way this program works is that it gets all the prime numbers and puts them in an arraylist. After that, it finds all the numbers that are greater than the previous prime factors.

Java Code:
```import java.util.Scanner;
import java.util.ArrayList;

public class PrimeFactors
{
static ArrayList<Double> primeList = new ArrayList<>();
static double range = 0;
static double maxPrime = 0;
static double primeTester = 0;

public static void main(String[] args)
{
Scanner input = new Scanner(System.in);

System.out.println("Up to what number would you like me to find prime numbers? ");
range = input.nextDouble();

double incrementer = 0;
double multiple = 2;

for (double i = 2; i < Math.sqrt(range); i++)
{
for (double j = 2; j < range;)
{
j = Math.pow(i, 2) + incrementer;

if(primeList.contains(j))
{
primeList.remove(j);
}

}

incrementer = 0;
multiple = 1+i;
}

System.out.println("\nWhat number inside the list would you like me to find the greatest prime factor");
primeTester = input.nextDouble();

System.out.println(greaterPrime());

}

{
for (double i = 2; i < range; i++)
{
}
}

{
for (Double double1 : primeList)
{
System.out.println(double1);
}
}

public static double greaterPrime()
{
double tempVar = 0;

for (int i = 0; i < primeList.size(); i++)
{
if(primeTester % primeList.get(i) == 0)
{
tempVar = primeList.get(i);
}

if(maxPrime < tempVar)
{
maxPrime = tempVar;
}
}

return maxPrime;
}
}```
Last edited by Deathslice; 01-27-2015 at 05:01 AM.  Reply With Quote

2. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Making this program more efficient

Your main problem is that you are repeatedly deleting a value from a list. With a regular ArrayList, that is extremely expensive because the ArrayList is backed by a regular array. You can't delete something from an array so you have to continually reallocate an array and recopy parts of it to "delete" something. And changing to a LinkedList didn't really help because it still must do a linear lookup to determine where to delete the node. What you need to do is to reread the optimized solution on Wikipedia and implement it as stated. Or use a BitSet as I suggested in the earlier thread. BTW, as a guideline, I can generate all primes up to 200,000,000 in less than 30 seconds. And my laptop is over 10 years old. So their algorithm is sound. The non-optimized algorithm is about 30 percent slower.

Regards,
Jim
Last edited by jim829; 01-27-2015 at 12:52 PM. Reason: typo  Reply With Quote

3. ## Re: Making this program more efficient

If you want to know whether or not i <= sqrt(n), you want to know whether or not i*i <= n; the second form doesn't need the expensive sqrt( ... ) method; also note that, except for the values 2 and 3, every prime is a multiple of 6 +/- 1; this removes 2/3 of the iterations.

Or use a sieve with a BitSet ...

kind regards,

Jos  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•