Originally Posted by
jamix Good point. That would be faster because it would halt right after we've found one prime factor (and half the time n would be divisible by 2).
Let me change the question. Determine the largest prime (if any) among 2-97 that divides arbitrary chosen integer n, that can be determined faster (on the average) than calculating the following:
gcd(97,n), then gcd(89,n), then gcd(83,n) and so forth until prime factor is found.
Hint: Think about some elementary factoring methods out there. Which method(s) are particularly fast at find smaller prime factors.