Improve speed of iteration and comparison

DangerousJeff
DangerousJeff used Ask the Experts™
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);

Open in new window


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);

Open in new window


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
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:
some suggestions on this thread;
there is aof course lots of literature about checking for primes

http://www.physicsforums.com/showthread.php?t=38437
C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

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.

Author

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);

Open in new window

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial