  # Improve speed of iteration and comparison

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...
JavaProgramming Theory Last Comment
DangerousJeff for_yan 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 TommySzalapski  THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform. for_yan there is aof course lots of literature about checking for primes TommySzalapski 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)). TommySzalapski 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. DangerousJeff 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);
`````` Java

Java is a platform-independent, object-oriented programming language and run-time environment, designed to have as few implementation dependencies as possible such that developers can write one set of code across all platforms using libraries. Most devices will not run Java natively, and require a run-time component to be installed in order to execute a Java program.

102K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts

TRUSTED BY           