MillerRabin.cpp

/*
  The implementation of Miller-Rabin Test with C++
  varified with ALDS1_1_C
  
  http://joisino.hatenablog.com/entry/2017/08/03/210000
  
  Copyright (c) 2017 joisino
  Released under the MIT license
  http://opensource.org/licenses/mit-license.php
 */

#include <bits/stdc++.h>

using namespace std;

struct Miller{
  const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
  // x^k (mod m)
  long long modpow( long long x, long long k, long long m ){
    long long res = 1;
    while( k ){
      if( k & 1 ){
        res = res * x % m;
      }
      k /= 2;
      x = x * x % m;
    }
    return res;
  }
  // check if n is prime
  bool check( long long n ){
    if( n < 2 ){
      return false;
    }
    long long d = n - 1;
    long long s = 0;
    while( d % 2 == 0 ){
      d /= 2;
      s++;
    }
    for( long long a : v ){
      if( a == n ){
        return true;
      }
      if( modpow( a , d , n ) != 1 ){
        bool ok = true;
        for( long long r = 0; r < s; r++ ){
          if( modpow( a, d * (1LL << r), n ) == n-1 ){
            ok = false;
            break;
          }
        }
        if( ok ){
          return false;
        }
      }
    }
    return true;
  }
};

Miller miller;

int main(){

  int n, a;
  int ans = 0;
  scanf( "%d" , &n );
  for( int i = 0 ; i < n; i++ ){
    scanf( "%d" , &a );
    if( miller.check( a ) ){
      ans++;
    }
  }
  printf( "%d\n" , ans );

  // bench
  /*
  const int MAX_N = 1000000000;
  const int loop = 1000000;
  mt19937 mt( 1234 );
  for( int i = 0; i < loop; i++ ){
    int n = mt() % MAX_N;
    miller.check( n );
  }
  */
  
  return 0;
}