PROBLEM LINK:Author: Rahim Mammadi DIFFICULTY:EasyMedium PREREQUISITES:Sieve of Eratosthenes PROBLEM:Given an array of N integers (all integers are up to $10^5$). Let's suppose we have taken a nonempty subset of this array. The magical value of this subset is (Number of distinct prime numbers that divides every number of the subset * the size of this subset). Find the subset with the maximum magical number and output this number. EXPLANATION:First of all, Number of distinct prime numbers that divide every number of the subset is equivalent to the number of prime factors of GCD of this subset. Let's try all possible GCDs. How's that possible? If you don't know Sieve then stop reading and take a look at this link. After that, try to figure out the solution yourself. What's the optimal subset for a certain GCD (let's say K) ?. Clearly, we can take a subset of all of its multiples in the array. Please note that the GCD of this subset would be K or one of its multiples, but that doesn't affect the answer (Why?). Because we will have the same subset when handling this (multiple of K) which is the real GCD and since it's a multiple of K, it has at least the same number of prime factors hence, the answer will be updated for sure. So we can safely assume the the GCD is equal to K with no problems. How to loop over the multiples of a number K?
So our code looks like this:
The complexity of this loop is: $$\sum_{i = 1}^{MaxValue} \frac{MaxValue}{i}$$ which is equal to: $$MaxValue * \sum_{i = 1}^{MaxValue} \frac{1}{i}$$ The sum of the series: $$\sum_{i = 1}^{MaxValue} \frac{1}{i} \approx log(MaxValue)$$ So total complexity is $MaxValue * log (MaxValue)$ There is also a part left for you, which is figuring the number of prime factors. This is easy, and can be done also while doing the Sieve approach (left for you), or you can check the codes. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 25 Nov '18, 01:20

Another approach: Using the sieve of Eratosthenes precompute two arrays  numbers of prime factors and divisor lists. Create a zeroinitialized array of useful numbers corresponding to each gcd value. For each element in the input array for each of its divisors add the contribution of the element to the useful number corresponding to the divisor. This contribution is the number of prime factors of the divisor. The answer is the maximum value in the resulting array. answered 27 Nov '18, 09:53

answered 27 Nov '18, 01:47

This is not the sieve of Eratosthenes. In the sieve of Eratosthenes you only loop over multiple of primes. You use the sieve of Eratosthenes to find numbers of prime factors, and do it once before running the test cases.