Thread: 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.

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.

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.

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.