1. ## Integer factorization

Is there a way to determine whether a given integer 'n' is divisible by any of the primes from 2-97, which can be determined faster than calculating gcd(2*3*5...*97, n)? Assume n is not bounded.

2. Originally Posted by jamix
Is there a way to determine whether a given integer 'n' is divisible by any of the primes from 2-97, which can be determined faster than calculating gcd(2*3*5...*97, n)? Assume n is not bounded.
If you are doing a computer program then I think it would be faster to tell the computer to calculate gcd(2,n),gcd(3,n), ... , gcd(97,n) and stop if it reaches a non-unit answer. That will tell you if the number if divisible or is it.

3. 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.

4. 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.
Starting with the lower primes (2,3,5...) will generally yield a solution faster than starting at the higher end (97,89,83,...)

If your computer can handle the number then calculate 1 time and use:
2*3*5*7*11* ... *79*83*89*97

5. It won't be faster. Remember I'm asking for the LARGEST prime factor in the set (2,97). If we start at 2, then we would have to test every single prime in the above set. If we start at 97, we can halt as soon as the first prime factor is found.

There are 25 primes from 2-97. I say start by calculating gcd(n,37*41*43*47*....97). This is the gcd of n with the largest 12 primes (the bigger half). If this equals 1, then repeat using smaller half of primes 2-31. Otherwise break the primes 37-97 into two half's and repeat this process starting with larger half (ie gcd(n, 71*....*97).

6. Originally Posted by jamix
It won't be faster. Remember I'm asking for the LARGEST prime factor in the set (2,97). If we start at 2, then we would have to test every single prime in the above set. If we start at 97, we can halt as soon as the first prime factor is found.

There are 25 primes from 2-97. I say start by calculating gcd(n,37*41*43*47*....97). This is the gcd of n with the largest 12 primes (the bigger half). If this equals 1, then repeat using smaller half of primes 2-31. Otherwise break the primes 37-97 into two half's and repeat this process starting with larger half (ie gcd(n, 71*....*97).
Try this:

Start at some number, say 987654321.
Then search increasing (from 2) and decreasing (from 97).
Do this for a few hundred thousand numbers and see which is faster?