Results 1 to 3 of 3
  1. #1
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default 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; 01-27-2015 at 05:01 AM.

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

    Default 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
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default 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
    Build a wall around Donald Trump; I'll pay for it.

Similar Threads

  1. Making this code more efficient...
    By andy_d in forum New To Java
    Replies: 2
    Last Post: 03-31-2014, 08:44 AM
  2. Replies: 14
    Last Post: 06-13-2013, 06:19 PM
  3. Replies: 5
    Last Post: 03-14-2013, 11:39 AM
  4. How to make my program more efficient?
    By LonelyClock in forum New To Java
    Replies: 9
    Last Post: 11-29-2011, 04:47 AM
  5. Need help making program more efficient
    By cid in forum New To Java
    Replies: 4
    Last Post: 06-30-2010, 07:22 PM

Posting Permissions

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