题目描述

给定一个长度为 n 的整数序列 a1,a2,…,an。

请你从中选出尽可能多的数。

要求满足如下两个条件之一：
仅选择一个数；

1.选择至少两个数，且所选择的数的最大公约数大于 1；
2.输出选出数的最大可能数量。

输入格式
第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
一个整数，表示选出数的最大可能数量。

数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10^5，1≤ai≤10^5。

样例

输入
3
2 3 4
输出
2

分解质因数，枚举

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+15;
int n,x;
int cnt[N];
int l=1;
void fj(int x){
    for (int i = 2; i <= sqrt(x); i ++ ){
        if(x%i==0)cnt[i]++;
        while(x%i==0){
            x/=i;
        }
    }
    if(x!=1)cnt[x]++;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> x;
        fj(x);
    }
    for (int i = N-15; i >1; i -- ){
        l=max(l,cnt[i]);
    }
    cout << l;
}