ミラーラビンアルゴリズム

ミラー・ラビンアルゴリズム:1つの数が素数であるかどうかを迅速に判断する
必要な定理:
最小Ferma定理:nが素数であれば(a^(n−1)))%nは1に等しい.
クイックモードべき乗
ミラー・ラビンアルゴリズムは,上記2つを組み合わせて,fmod(a,n−1,n)の値が1であるか否かを絶えず判断することによって判断する.これは確率アルゴリズムであり,1であれば素数とは限らず,1でなければ必ず合数である.繰り返し判断すると確率が極めて小さくなります.
アルゴリズムテンプレート:

#include <iostream>

using namespace std;

int fmod(int a, int b, int c)//     
{
	if(b == 1) return a;
	int t = fmod(a, b / 2, c);
	t = (t * t) % c;
	if(b & 1) t = (t * a) % c;
	return t;
}

int check(int n)//  -    
{
	srand(time(0));
	for(int i = 0; i < 100; ++ i)
	{
		if(fmod(rand() % (n - 1) + 1, n - 1, n) != 1)//a      ，        ；a    [1,n-1]，          n   ， n a   
			return 0;
	}
	return 1;
}

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		if(n < 2)
		{
			printf("   
");
			continue;
		}
		if(check(n))
			printf("  
");
		else
			printf("   
");
	}
	return 0;
}