Useful Number - Nov LunchTime

general
, ,
1

My approach for this question is -

1 - Use sieve of eratosthenes for Unique Prime factor for any Number : -

prime = [1] * (10 ** 5 + 5)

divPrime = [0]*(10**5+5)
prime[0] = 0
prime[1] = 0
prime[2] = 1
for i in range(2, 10 ** 5 + 5):
    if prime[i] == 1:
        divPrime[i]+=1
        b.append(i)
        for j in range(2 * i, 10 ** 5 + 5, i):
            prime[j] = 0
            divPrime[j]+=1

No of Unique Prime Factor of any Number stored in divPrime Array

2- *iterate i loop form 2 to max(a) and if element of Input array is divided by i then count+=1 *

3 -ans will be the calculate by *ans = max(ans,divPrime[i]**count)

but above approach give me 30 points .

How to optimize this code ?

Code Link - https://www.codechef.com/viewsolution/21692429

2

Initially you should calculate frequency of each number of array.
Let us consider for now that the number be z where
z = p1p2p3 … *pk where count of distinct primes is equal to k. Now for calculating numbers present in array and also divisible by z , you have to just iterate through multiples of z whose complexity is logz(100000).

Now any number less than or equal to 100000 can be represented as a product of at max primes.
(2 X 3 X 5 x 7 x 11 x 13 > 100000). So you can perform recursion and find all possible products of primes.The maximum depth of recursion would easily fit in the time limit.

Hope this helps. :slight_smile:

2 Likes
3

Any number up to 10^5 can have maximum 6 distinct prime factor. This observation will help you with optimization. I solved this question using this observation.

2 Likes
4

I’ve figured out this approach after the contest. Hope this helps you.

  • Find the number of prime divisors of each number in [0, 1e5] using sieve. Let this array be prime_div[].
  • For each divisor d of Ai, do freq[d]++
  • Now the answer is max(prime_div[i] * freq[i]) for all i in the range of [2, 1e5]

Here’s my solution

4 Likes
5

No need to calculate frequencies. :slight_smile:

https://www.codechef.com/viewsolution/21698376

6

One thing I would suggest - try PyPy instead of regular Python.

7

You could instead keep lists of prime factors instead of just numbers.

https://www.codechef.com/viewsolution/21698693