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:
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:
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...
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...
Last Comment
ASKER CERTIFIED SOLUTION
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.
some suggestions on this thread;
there is aof course lots of literature about checking for primes
http://www.physicsforums.com/showthread.php?t=38437
there is aof course lots of literature about checking for primes
http://www.physicsforums.com/showthread.php?t=38437
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)).
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.
ASKER
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
no sense to try those which end in 5 and 10