fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 1000002
  4. int arr[MAX];
  5. bool vis[MAX],invis[MAX];
  6. void solve()
  7. {
  8.  
  9. int i,j,n,cnt=0,mx=0;
  10. cin>>n;
  11. for(i=0;i<n;++i)
  12. {
  13.     cin>>arr[i];
  14.     invis[arr[i]]=1;
  15.     mx=max(mx,arr[i]);
  16. }
  17.  
  18. sort(arr,arr+n);
  19.  
  20. for(i=0;i<n;++i)
  21. {   bool flag=0;
  22.  
  23.     if(vis[arr[i]])
  24.         continue;
  25.  
  26.     for(j=2*arr[i]; j<=mx; j+=arr[i])
  27.     {
  28.         if(invis[j])
  29.             vis[j]=1,flag=1;
  30.     }
  31.     if(flag)
  32.         vis[arr[i]]=1;
  33. }
  34. for(i=0;i<n;++i)
  35.     if(!vis[arr[i]])++cnt;
  36.  
  37. cout<<cnt;
  38. }
  39. int main()
  40. {
  41. ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  42. solve();
  43. }
  44.  
Success #stdin #stdout 0s 21104KB
comments (?)
stdin
copy 
5
2 3 4 5 6
stdout
copy 
1
https://ideone.com/9yztbn
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!