fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll int 
  4. #define maxn 20000002
  5. bool isprime[maxn+1];
  6. bool two_primes[maxn+1];
  7. void sieve(){
  8.     isprime[0]=isprime[1]=false;
  9.     for(ll i=2;i<=(ll)sqrt(maxn);i++){
  10.         if(isprime[i]){
  11.             for(ll j=i*i;j<=maxn;j+=i) isprime[j]=false;
  12.         }
  13.     }
  14. }
  15. void sieve_2(){
  16.     two_primes[0]=two_primes[1]=false;
  17.     for(ll i=2;i<=(ll)sqrt(maxn);i++){
  18.         if(isprime[i]){
  19.             two_primes[i]=false;
  20.             for(ll j=i*i;j<=maxn;j+=i){
  21.                 if(!isprime[j/i]) two_primes[j]=false;
  22.             }
  23.         }
  24.  
  25.     }
  26. }
  27. int main(){
  28.     ios_base::sync_with_stdio(0);
  29.     cin.tie(0);
  30.  
  31.     memset(isprime,true,sizeof(isprime));
  32.     memset(two_primes,true,sizeof(two_primes));
  33.     sieve();
  34.     sieve_2();
  35.  
  36.     ll n;
  37.     cin>>n;
  38.     ll res = 0;
  39.     for(ll i=0;i<n;i++){
  40.         ll x;
  41.         cin>>x;
  42.         if(two_primes[x] && !isprime[x]){
  43.             // cout<<"db:  "<<x<<'\n';
  44.             res++;
  45.         }
  46.     }
  47.     // cout<<"res: "<<res;
  48.     cout<<res;
  49.     return 0;
  50. }
Success #stdin #stdout 0.38s 42440KB
comments (?)
stdin 
3
3 6 9
stdout 
2
https://ideone.com/czzVfv
language:
C++14 (gcc 8.3)
created:
2 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!