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

    Default Nested For loop causing my program to crash.

    Can someone check my implementation of the nested for loop. I thought it was going to go smoothly but apparently not.

    Purpose: This program is meant to print out all the prime numbers up to a certain range using the algorithm Sieve of Eratosthenes.

    Update output: Works as expected.

    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-23-2015 at 07:57 PM.

  2. #2
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    Well I fixed the crashing problem but now I have a new problem. It's printing every single number and not every prime number.

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

    Default Re: Nested For loop causing my program to crash.

    I have done a sieve before but your inner loop looks very strange to me. In any event you are not changing the value of j in your inner loop.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  4. #4
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    I figured out the problem. The problem was with the addinteger function. It was filling up the arrayList with integers and I was comparing those integers with double. This meant that none of the even numbers or composite numbers got removed.

    I'll update my main post now. If you know a way for me to shorten my code, please let me know.
    Last edited by Deathslice; 01-23-2015 at 06:23 PM.

  5. #5
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    There was a couple of lingering logical errors left in the program and I have fixed those too. Thanks jim for your help.

    Update: My main post has now been updated again.

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

    Default Re: Nested For loop causing my program to crash.

    Quote Originally Posted by Deathslice View Post
    If you know way for me to shorten my code, please let me know.
    Well, I know it can be shorter (but not necessarily better). But the important thing is that it works. For algorithms like this you may want to check out the BitSet class. The bit set is a convenient class for marking locations/positions which is what the sieve is all about.

    In general, first worry about efficiency more than length. Second, don't worry about either too much. If you want to optimize your code, focus on the algorithm over the implementation. E.g. for a sort, don't do a bubble sort (except for learning purposes), do a quick sort or some other type of sort. But this is all "sorted out" before you start to code (pun intended).

    Regards,
    Jim
    Last edited by jim829; 01-23-2015 at 06:31 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  7. #7
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    I decided to make the program a little more advance by making the program find the largest prime factor in a number.

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

    Default Re: Nested For loop causing my program to crash.

    After looking at your algorithm, I am not sure you are doing an actual sieve. According to some articles I have read if you divide by previously calculated primes, that is not a sieve. The sieve of Eratosthenes basically says, start with the first prime n, and mark every nth value. The next unmarked value from the beginning will be a prime. Then for that prime n, mark off every nth value. The next unmarked value will be the next prime. The point being is that the actual sieve is more of a bookkeeping algorithm than a mathematical one.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  9. #9
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    Are you sure? I'm using modulus to find the greatest prime factor in a given number(the number the user inputs). The whole sieve thing is happening in the public static main(look at the nested for loop); not the greaterPrime function(this function just uses all the prime numbers in the arraylist to find the greatest prime factor. For example the greatest prime factor of 10 is 5 and the factors of 10 are 2 and 5).
    Last edited by Deathslice; 01-23-2015 at 08:05 PM.

  10. #10
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    In response to the point you made that the sieve of Eratosthenes is a bookkeeping algorithm, That is exactly what my function is doing. When the function finds an even number or composite number it removes it or "blackens it out". Whatever remains in the ArrayList are the real prime numbers.

    To put it more bluntly, let's say you have a grid of numbers from 1-100 with one being excluded from the list of prime numbers.
    My program is walking along the grid and removing every multiple that the first prime number has. Once that is done, the next number is obviously a prime number because it wasn't removed. Then it keeps on repeating until you get a number greater than the sqrt of n with n been a number greater than 1.
    Last edited by Deathslice; 01-23-2015 at 08:04 PM.

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

    Default Re: Nested For loop causing my program to crash.

    My point is that you don't need to determine if the value is composite or not. Primes just appear automatically due to the nature of the sieve. Let's say you print out 2. Then go thru the array and set every other second value to -1. Then the next one that is not -1 is a prime (it is 3). Then go thru the array from there and set every third value to -1. The next one that is not -1 is 5. And you keep on repeating this. When you are done, the only positive numbers left will be primes.

    And I am not making any claim on which is more efficient for any size of numbers. In any event, here are some articles I found that I also mentioned in an earlier thread on this subject.

    Sieve of Eratosthenes - Wikipedia, the free encyclopedia
    http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    The second one discusses what the sieve is and is not. Quite illuminating actually.

    Regards,
    Jim
    Last edited by jim829; 01-23-2015 at 08:11 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  12. #12
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

    Default Re: Nested For loop causing my program to crash.

    Well thanks anyways. It was nice chatting with you.

    Also I will admit that it is really slow once the number is 100000. :)
    Last edited by Deathslice; 01-23-2015 at 08:12 PM.

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

    Default Re: Nested For loop causing my program to crash.

    Quote Originally Posted by Deathslice View Post
    Well thanks anyways. It was nice chatting with you.

    Also I will admit that it is really slow once the number is 100000. :)
    Actually, after all my pontificating I think I was probably wrong about your implementation. I got caught up in the greaterPrime method which is not part of the actual algorithm. Mea culpa.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  14. #14
    Deathslice is offline Member
    Join Date
    Jan 2015
    Location
    Miami, FL
    Posts
    86
    Rep Power
    0

Similar Threads

  1. Replies: 5
    Last Post: 11-25-2012, 11:57 PM
  2. While loop makes program crash
    By atiyarose17 in forum New To Java
    Replies: 5
    Last Post: 10-10-2012, 05:53 AM
  3. Replies: 7
    Last Post: 05-03-2011, 06:41 PM
  4. Recursive for loop causing problems
    By Catfish1 in forum New To Java
    Replies: 2
    Last Post: 02-22-2011, 03:12 PM
  5. Help Making a program not crash
    By Lifeis2evil in forum New To Java
    Replies: 2
    Last Post: 12-10-2008, 03:10 AM

Posting Permissions

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