Results 1 to 3 of 3
 01272015, 05:58 AM #1Member
 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(); addIntegers(); double incrementer = 0; double multiple = 2; double add = 1; 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 = multiple * add; add++; } incrementer = 0; multiple = 1+i; add = 1; } printPrimeNumbers(); 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()); } public static void addIntegers() { for (double i = 2; i < range; i++) { primeList.add(i); } } public static void printPrimeNumbers() { 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; 01272015 at 06:01 AM.
 01272015, 07:19 AM #2Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 15
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 nonoptimized algorithm is about 30 percent slower.
Regards,
JimLast edited by jim829; 01272015 at 01:52 PM. Reason: typo
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 01272015, 10:02 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 29
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,
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

Making this code more efficient...
By andy_d in forum New To JavaReplies: 2Last Post: 03312014, 09:44 AM 
My program has to run in less than a minute. Can anyone help make my code efficient?
By jamgor in forum New To JavaReplies: 14Last Post: 06132013, 07:19 PM 
Anyway I could "clean up" or make this simple program more efficient/better?
By psx2514 in forum New To JavaReplies: 5Last Post: 03142013, 12:39 PM 
How to make my program more efficient?
By LonelyClock in forum New To JavaReplies: 9Last Post: 11292011, 05:47 AM 
Need help making program more efficient
By cid in forum New To JavaReplies: 4Last Post: 06302010, 08:22 PM
Bookmarks