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.

Printable View

- April 13th 2009, 03:59 PMjamixInteger 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.

- April 14th 2009, 11:38 AMThePerfectHacker
- April 14th 2009, 01:02 PMjamix
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. - April 15th 2009, 07:36 AMaidan
- April 15th 2009, 10:08 AMjamix
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). - April 15th 2009, 02:27 PMaidan