Best approach please?

help
,
1

given array of integers and you find the most common prime divisor for numbers in this array and count of his multiples in array ?
ex.
test 1
5
1 2 3 10 20
out
2 3

test 2
5
4 4 4 4 3
out
2 4

2

any help…

3

What are the constraints on n and A_i?

2 Likes
4

1<=n<=1000
1<=ai<=10^9

5

We can pre compute all the primes till \sqrt{A_i} using sieve.
Next, create a container to store the count for each prime.
Now loop through the given array, and increment the prime count for each A_i by running a second loop through our prime list.

Complexity: O(\sqrt{A_i} \cdot n)

3 Likes
6

I think i did but my solution give me memory limit exceed
this ::

7

You are generating all primes less than A_{max}. This will give MLE and probably TLE too. It’s enough to compute until \sqrt{A_{max}}. We can always check a number > A_{max} is prime or not by checking if it has a factor from 1 : \sqrt{A_{max}}.

2 Likes
8

Here A_{max} \le10^9. So generating primes upto 31623 will be enough.

2 Likes
9

but test case like this
5
7 7 7 7 2
out
2 1
if you generate prime numbers until sqrt(mx) but it correct output 7 4

10

That’s right. And also you don’t have to find the max element and generate till that. Just precompute it for 32,000 before taking any input.

1 Like
11

Which is why we loop through the given array first, and count the occurrence of each prime. As you count keep dividing it by that prime. The final value of Ai is your prime that’s greater that sqrt A. If it ends up being 1, there is no bigger prime.

1 Like
12

My bad. There might be a flaw here. The Ai that remains can also be a product of two larger primes.

[EDIT]: Nevermind. Product of two larger numbers will overshoot Amax. So the remaining number has to be the largest prime in Ai.

13

Here, consider A_i.
If there are no prime factors \le \sqrt{A_{max}}, then A_i is definitely prime (for given constraints). So, you should consider 7 as prime and increment the answer.

2 Likes
14

No. For A_i \le 10^9, checking primes upto \sqrt{10^9} is enough.

2 Likes
15

Oh! Beautiful then. I’m not really good with primes and number theory. :3

1 Like
16

may be we can optimize this solution to passed

17

I guess this has the same approach. I guess by optimise you mean modify? There is no big modification. If the number you get is a composite number, just print any prime factor of the number you get. It should work.

18

so what is the efficient approach to do that we have prime factors but large than sqrt(Ai)

19

Calculate sieve upto 31623.

  1. Create a map to store frequencies of prime factors.
  2. For each A_i.
    a. Count prime factors and increment in map.
    b. If no prime factors were found, then increment map [A_i] itself.
  3. Iterate over map to find final ans.
1 Like
20

may be like this WCUJ5j - Online C++0x Compiler & Debugging Tool - Ideone.com
but give Runtime error