I am given a list of integers (up to 1000) which multiply to a given integer n .
I need to find the highest power among all the divisors of the integer n .
For instance : 4,7,8 multiply to 224 and the highest power will then be 5 since 224=2^2*7*2^3=2^5*7.
The problem is, the 1000 integers can be as large as 2^64, hence n is very large.
What is a great algorithm to solve this ?
Difficult. I'd start checking small primes first (in your example: 4, 7, 8. The product has a factor 2^5. You divide by the powers of two, leaving 1, 7, 1. Then you do the same for 3, 5, 7 etc. up to X).
Now you need to find a larger prime p > X that is a higher power than the highest you found. Spending lots of time to find prime factors that occur only once seems wasteful. You need primes that are factors of multiple numbers. Calculate the gcd of each pair of numbers and look at prime factors of these numbers. There are lots of details that need working out, that's why I started with "difficult".
Worst case you can't easily find any prime that occurs twice, so you need to check if each of the numbers contains the square of a prime as factor.
As an example: You checked for factors up to 1000, and you found that the highest power of a prime was 83^3. So now you need to find a larger prime that is a fourth power or show there is none. Calculate the pairwise gcd's (greatest common divisor). A large prime could be a divisor of multiple of these gcd's coming from four different numbers, or p could be factor of three gcd's, with p^2 a factor of one number etc.
To clarify the principle: Say you have two HUGE numbers x and y, and you want to know which is the highest power of a prime which divides xy. You could factor x and y and go from there. If they are both primes or products of two large primes, say x = p or pq, and y = r or rs, this takes a long time.
Now calculate the gcd of x and y. If the greatest common divisor is z > 1, then z is a factor of x and y, so z^2 is a factor of xy. If the greatest common divisor is 1, then x and y have no common factor. Since we don't need factors that are not square, we look for squares and higher factors. For that you only need to divide by factors up to x^(1/3) or y^(1/3).