HDUOJ 2138 How many prime numbers

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#define CLOSE() ios::sync_with_stdio(false)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
const int maxn = 100005;
using LL = long long;
using UI = unsigned int;
using namespace std;
//------------------------------------------------------------------------------------------//
//暴力法，乘法速度慢，用i*i逾時，sqrt能過，貌似sqrt是用牛頓疊代還是二分實作的？
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		int cnt = 0;
		while (n--) {
			int x;
			scanf("%d", &x);
			int flag = 1;
			//注意sqrt寫外面
			int t = sqrt(x)+1;
			for (int j = 2; j < t; ++j) {
				if (x % j == 0) {
					flag = 0;
					break;
				}
			}
			if (flag) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}



//Miller_Rabin算法
//費馬小定理：假設p是質數，那麼對任意a，a^(p-1)=1(mod p)。
//利用這一定理，隻要對任意取s次a屬于[1, p-1]，mod = 1，則p為素數。

//二次探測定理：p為素數，x方 = 1（mod p）解為x = 1 || x = p-1.
//把p-1拆分成為二進制表示2^t*u，令x[0] = a^u，随後平方t次，若出現
//某次x[i] mod p = 1但是x[i-1] != 1 && x[i-1] != p-1,則p非素數。
//若資料大，則将乘法也用快速幂的方法表示。
const int S = 4;

LL q_pow(LL a, LL n, LL mod) {
	LL ret = 1;
	while (n) {
		if (n & 1) ret = ret*a%mod;
		n >>= 1;
		a = a*a%mod;
	}
	return ret;
}

bool Miller_Rabin(LL n) {
	if (n == 2) return true;
	if (n < 2 || !(n & 1)) return false;
	int t = 0;
	LL a, x, y, u = n - 1;
	while ((u & 1) == 0) t++, u >>= 1;
	for (int i = 0; i < S; i++) {
		a = rand() % (n - 1) + 1;
		x = q_pow(a, u, n);
		for (int j = 0; j < t; j++) {
			y = x*x%n;
			if (y == 1 && x != 1 && x != n - 1)
				return false;
			x = y;
		}
		if (x != 1) return false;
	}
	return true;
}


int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		int x, cnt = 0;
		while (n--) {
			scanf("%d", &x);
			if (Miller_Rabin(x)) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}