Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long int
- using namespace std;
- int const MAXN=2e7+500;
- map<int,int> mp;
- int p[MAXN];
- vector <int> v;
- void ff (int n){
- set <int> s;
- int pf_idx=0,pf=v[pf_idx];
- while (pf*pf<=n){
- while (n%pf==0) {n/=pf, s.insert(pf); };
- pf=v[++pf_idx];
- }
- if (n!=1) s.insert(n);
- for (auto cur : s) mp[cur]++;
- }
- int main (){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- //freopen("input.txt","r",stdin);
- int n;
- cin>>n;
- int g=0;
- int a[n];
- for (int i=0;i<n;i++){
- cin>>a[i];
- g=__gcd(g,a[i]);
- }
- int ans=1e9;
- for (int i=0;i<n;i++) a[i]/=g;
- for (int i=2;i<MAXN;i++)
- if (p[i]==0){
- v.push_back(i);
- for (int j=2*i;j<MAXN;j+=i)
- p[j]=1;
- }
- for (int i=0;i<n;i++) ff(a[i]);
- for (auto cur : mp){
- if (cur.first!=1)
- ans=min(ans,n-cur.second);
- }
- if (ans ==1e9) cout<<-1;
- else cout<<ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement