Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Ways to make this loop more efficient?

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Ways to make this loop more efficient?

    Hello, this is a loop I've written to find all the prime numbers up to the input from the user (n)
    I can see that this one has many steps to perform and so I am looking for a way to improve it's efficency.

          for(int m = 2; m < n; m++) {
             boolean isPrime = true; 
             for (int c = 2; c < m; c++){
                if(m%c == 0) isPrime = false; //is not a prime
     
             }
     
             if(isPrime == true) {            
                System.out.println(m);
             }         
          }

    I'd really like to use 'break' somewhere, somehow.

    Could you please help me, or give me a few tips?

    Thank you for your time and knowledge


  2. #2
    Member Chris.Brown.SPE's Avatar
    Join Date
    May 2008
    Location
    Fort Wayne, Indiana
    Posts
    190
    Thanks
    1
    Thanked 31 Times in 31 Posts

    Default Re: Ways to make this loop more efficient?

    Two things that will make your loop much much better.

    1. You do not need a break!!! The idea that you need one is just due to ignorance of the power of for loops. Please dont take this as an insult, it took me years to really realize what the possibilities were. Add your flag to the for loop boolean check just like you would in an if statement. "for(int c = 2; c < m && isPrime == true; c++)". It will break as soon as isPrime is made false.

    2. As for making it more efficient, there is one thing you could do to make it much faster. You are checking the number against all number less than it. Using a bit of logic you can simplify the number of numbers needed to be checked. So what do we know about prime numbers, they are only divisible by 1 and itself. All other numbers are divisible by some other prime number. Boom! There's no sense in checking it against non prime numbers. If a number is not divisible by 2 or 3 then it is unnecessary to divide it by 4,6,9,12,16,18 and so on because all those numbers have roots in 2 and 3. Make sense? Keep a list of all found prime numbers and only check against them. You can decrease it even further by doing a mathematical check. If 3,583 is not divisible by 2 then you know it will not be divisible by anything higher than 1791 which is 3,583/2. Similarly if not divisible by 3 then there is no need to check any numbers greater than <your value>/3.
    Writing code is your job, helping you fix and understand it is mine.

    <-- Be sure to thank and REP (Star icon) those who have helped you. They appreciate it!

  3. #3
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Ways to make this loop more efficient?

    Considering just efficiency, using a break is can be more efficient than adding an extra bit of code to be executed every time a loop goes around.

    It does depend on the logic in the loop. If the test is always being made in the loop, then there is no improvement.
    If you don't understand my answer, don't ignore it, ask a question.

  4. #4
    Member Chris.Brown.SPE's Avatar
    Join Date
    May 2008
    Location
    Fort Wayne, Indiana
    Posts
    190
    Thanks
    1
    Thanked 31 Times in 31 Posts

    Default Re: Ways to make this loop more efficient?

    Agreed Norm. If efficiency is all you care about then "best practices" go out the window and using a break would eliminate the boolean check for each loop. This is getting close to my favorite super efficient for loop, find a way to remove the boolean check all together and surround the for loop in a try catch and do nothing on the catch. Great for iterating through lists super fast. It throws an index out of bounds exception and moves on.

    For a comparison, i coded this up and was able to find all prime numbers up to 10,000,000 in 3118 milliseconds where the original posted code could only do 110,000 in the same amount of time (System.out's were removed for this test). It's amazing what kind of overhead you can get with nested for loops as it scales up.
    Writing code is your job, helping you fix and understand it is mine.

    <-- Be sure to thank and REP (Star icon) those who have helped you. They appreciate it!

  5. #5
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Ways to make this loop more efficient?

    A suggestion for an alternative algorithm: Sieve of Eratosthenes - Wikipedia, the free encyclopedia, perhaps compare the complexity of that algorithm vs the nested look you posted in the original post.

Similar Threads

  1. How to make this method more efficient?
    By failingcompsci in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 11th, 2012, 05:03 PM
  2. Wondering if there's a way to make this more efficient.
    By mjr in forum Algorithms & Recursion
    Replies: 2
    Last Post: June 29th, 2012, 06:59 PM
  3. How to make code more efficient?
    By Apocalypse in forum Java Theory & Questions
    Replies: 2
    Last Post: October 21st, 2011, 09:07 AM
  4. How to make a simple and efficient web control panel.
    By kelsmith11 in forum Java Theory & Questions
    Replies: 3
    Last Post: October 18th, 2011, 02:28 PM
  5. Replies: 4
    Last Post: September 5th, 2010, 10:29 AM