1

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 ?

  • This is a trick question. The largest prime factor of each one of the integers (including the integers themselves, if they're prime), will always be the same as the largest prime factor of their product. Fundamental math. – Sam Varshavchik Oct 30 '16 at 16:36
  • Actually I'm not seeking the largest prime, but the largest power of all primes, that is the highest k such that d^k divides n for all d. It's max{ k such that d^k | n where d is a divisor of n } –  Oct 30 '16 at 16:40
  • Doesn't matter. After computing the primes of each number, you just need to tally them up together. For example, with the example of 4, 7, and 8, you get 2*2, 7, 2*2*2. You've got five 2s there, that's your answer. You *do not* need to multiply them together, just factor each integer individually, and tally them together. Basic math. – Sam Varshavchik Oct 30 '16 at 16:44
  • Well .. That's actually what I did, I've explained my approach, factoring each number then counting the occurences of primes and taking the maximum. It works perfectly for small numbers as in the example, but let's take 985528436837146801 for example (as one of those 1000 numbers). It has taken me 7 seconds to factor it on its own. –  Oct 30 '16 at 16:48
  • 3
    Then this is nothing more than a question about the most efficient way to find the prime factors of a number. I'm sure there are plenty of prior questions on this topic matter, somewhere around here... Run a Google search for "Sieve of Eratothenes". – Sam Varshavchik Oct 30 '16 at 16:50
  • Already searched for sieves too(Eratosthenes's and Atkin's), the problem I face is that I need to generate the primes up to 10^9 as a precomputation. But storing them in a vector and iterating over them is once again taking a lot of time. –  Oct 30 '16 at 16:56
  • @SamVarshavchik: Wrong. When steps in solving a problem take long time, don't think "how can I do this step faster", think "how can I solve the problem without that step". – gnasher729 Oct 30 '16 at 16:57
  • 2
    @SamVarshavchik: And a sieve is quite useless to find factors of _one_ large number, or to find factors of 1,000 numbers up to 2^64. – gnasher729 Oct 30 '16 at 17:16
  • It looks like you cannot do much faster than that, otherwise you could use your method for mass factorisation of integers. – n. m. could be an AI Oct 30 '16 at 17:31
  • Why does this code need to be optimized or optimal? – Thomas Matthews Oct 30 '16 at 17:39
  • It needs to be optimized because the `for` loop (specifically the `i=i+2` part) checks every odd number up the square root of the number. That about 1 billion divisions when the input number has an 18 digits. That takes a long time. – user3386109 Oct 30 '16 at 17:45
  • In order for the answer to be greater than 1, the input must either be a perfect square, or the input must have at least 3 factors. If the input is a perfect square, then you only need to be able to factor the square root of the number, which requires a list of primes up to the fourth root of the number. If the number has 3 factors, then at least on of the those factors must be less than or equal to the cube root of the number. There are more details to work out, but you should be able to solve the problem given the list of primes less than 2642246. – user3386109 Oct 30 '16 at 18:13
  • @user3386109 What's the problem with having exactly 2 factors ? –  Oct 30 '16 at 20:21
  • If the number has exactly 2 factors, then what is the largest power among the divisors? – user3386109 Oct 31 '16 at 04:40
  • @user3386109, then don't check every odd number. Familiarise yourself with _prime wheels_ and the prime number theorem. – Michael Foukarakis Dec 25 '16 at 14:13

1 Answers1

5

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

gnasher729
  • 51,477
  • 5
  • 75
  • 98
  • @Guru: You don't need to factor this large number at all unless it has a common factor with some other number, since if it is a prime or factor of two large primes, but it has no common factor with any other number, you only get a power 1. You _might_ need to look for square factors if you can't find any squares, but that only requires factors up to about 3 million. – gnasher729 Oct 30 '16 at 17:05
  • I'm trying to understand your approach .. But what if the input consists of 500 times the number 985528436837146801 . The result should be 1000 because the resulting integer is equal to 992737849^1000 .. –  Oct 30 '16 at 17:23
  • You would find quickly that all numbers have the factor 985528436837146801, so you know you have a 500th power. Then you need to check whether 985528436837146801 is a square or has a square factor. Checking that it is square is very quick. To check if there is a square factor, you only need to remove factors up to x^(1/3). – gnasher729 Oct 30 '16 at 17:30
  • 1
    If you are taking 6-7 seconds to factorize 985528436837146801 then you already have a problem with the efficiency of your factorizing algorithm. The second return of the search "factorize big number online" was a web-site that found the solution 992737849*992737849 in under 0.005 seconds. So improving factorizing time may be sufficient to solve your TLE problems. – Penguino Oct 30 '16 at 21:55