Link to problem :https://codeforces.net/contest/1034/problem/A
Link to my submission: https://codeforces.net/contest/1034/submission/46372547
My approach: I divided the vector of the numbers by their gcd. Then I tried to find largest subsequence having gcd greater than 1. To do that , I used the Sieve of Eratosthenes to calculate least prime factor of every number upto 1.5*10^7 and stored it in array Primes. In the factorise function , I just increase the count of divisors and then return the answer(n-count of the divisor that occurred maximum number of times).
My code gives wrong answer for test case #9. The different between jury's answer and mine is small though . Also I have read the editorial and my approach is same as that of the editorial . I think the problem is with the sieve maybe , should it be in linear time? . Thank you .
Your program outputs 3
Thank you for your insight . I fixed the code and got AC .
If you know Bangla, then you can understand it from here. You can also use google translator.