Codeforce #511(Div 2) C. Enlarge GCD

Mr. F has n positive integers, a1,a2,…,an.
He thinks the greatest common divisor of these integers is too small. So he wants to enlarge it by removing some of the integers.
But this problem is too simple for him, so he does not want to do it by himself. If you help him, he will give you some scores in reward.
Your task is to calculate the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.
Input
The first line contains an integer nn (2≤n≤3⋅105) — the number of integers Mr. F has.
The second line contains nn integers, a1,a2,…,an (1≤ai≤1.5⋅107).
Output
Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.
You should not remove all of the integers.
If there is no solution, print «-1» (without quotes).
Examples
Input

3
1 2 4

Output

1

Input

4
6 9 15 30

Output

2

Input

3
1 1 1

Output

-1

Note
In the first example, the greatest common divisor is 1 in the beginning. You can remove 1 so that the greatest common divisor is enlarged to 2. The answer is 1.
In the second example, the greatest common divisor is 3 in the beginning. You can remove 6 and 9 so that the greatest common divisor is enlarged to 15. There is no solution which removes only one integer. So the answer is 2.
In the third example, there is no solution to enlarge the greatest common divisor. So the answer is −1.
제목: n개 수를 드리겠습니다. 최소 n개 수 중 몇 개를 삭제하면 나머지 수의 최대 공약수가 원래 n개 수의 최대 공약수보다 큽니다.
사고방식: 먼저 n개수의 최대 공약수를 찾아낸 다음에 n개수를 순서대로 그들의 최대 공약수를 제외하고 새로운 N개수를 얻는다.이 N 개수의 최대 공약수는 1이다.
그리고 이 N개의 새로운 수 [유일분해정리]를 분해한다.통계는 각 소수의 개수로 분해된다.가장 많은 것은 m개수를 제거한 후 남은 것이다
수의 최대 공약수.m=n(n개수)-num[수량이 가장 많은 소수];(num는 각 소수의 개수를 기록한다)
코드:
여기에 소수 타표보다 더 효율적인 소수 체를 운용했다.https://blog.csdn.net/weixin_45177251/article/details/106130112

#include
#include
#include
#include
using namespace std;
int a[300010];
int cnt[15000010];
bool book[15000010];
int su[15000010];
int r;
int gcd(int a,int b)//          
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
void prime()// 1~15000000   
{
    memset(book,0,sizeof(book));
    book[0]=book[1]=1;
    for(int i=2; i<15000000; i++)
    {
        if(book[i]==0)
        {
            su[r++]=i;
        }
        for(int j=0; j1)
                cnt[a[i]]++;
        }
        int ans=n;
        for(int i=2; i<15000000; i++)
            ans=min(ans,n-cnt[i]);
        if(ans==n)
            printf("-1
");
        else
            printf("%d
",ans);
    }
    return 0;
}