# Improve speed of iteration and comparison on
Hi there,

First time I've asked a question, so here goes...

I have a simple programming problem, my code works, but it needs to be a bit faster if that's possible.

Fragment:
``````	int num = 127 // could be as large as 999999937
int divby = 2;
while(num % divby != 0) {
divby++;
}
System.out.println(divby);
``````

The above code gets passed in an integer (num) and I need to find the first integer that it will divide by. This runs into issues if num ends up being a very large prime number, like 999999937.

Second iteration of the above code:
``````	int num = 127 // could be as large as 999999937
int divby = 2;
if (num % divby !=0) {
divby = 3;
while(num % divby != 0) {
divby+=2;
}
}
System.out.println(divby);
``````

This is a pretty good improvement, takes half the time, but its still a touch too slow.
Basically if it doesn't divide by 2, then only check odd numbers from then on.

Are there any other obvious improvements I can make here? Other than prechecking for really big prime numbers...
Comment
Watch Question

Do more with EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Awarded 2011
Awarded 2011

Commented:
You can do the same thing with division by five - if it does not end with 5 or zero
no sense to try those which end in 5 and 10

Awarded 2010
Top Expert 2013
Commented:
For starters, you can stop when you get to sqrt(num) instead of running all the way to num. If you haven't found a divisor that's less than the square root, then there isn't going to be one that's bigger since they come in pairs.
Awarded 2011
Awarded 2011

Commented:
there is aof course lots of literature about checking for primes

Awarded 2010
Top Expert 2013

Commented:
The only way to be sure is to test if it's divisible by every prime < sqrt(num) So there really isn't any foolproof way to make it faster than O(sqrt(n)).
Awarded 2010
Top Expert 2013

Commented:
As that article mentions, if you could find a better way, you could break public/private key incryption. So you can rest assured that yours is about as good as it gets. There are faster ways that occasionally give the wrong answer, but are usually right.

Commented:
Awesome, stopping at the square root did it very nicely, always something obvious!

``````	int sqrt = (int)Math.sqrt(num); // find sqrt of current large number
int num = 127 // could be as large as 999999937
int divby = 2;
if (num % divby !=0) { // can we divide large number by 2?
// no? ok, lets check the other odd numbers upto sqrt
for(divby = 3;num%divby != 0;divby+=2)
{ if(divby>sqrt+1){divby=num-2;} }
}
}
System.out.println(divby);
``````

Do more with 