素数检测.txt

一些数论题目的代码

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
using namespace std;

#define NMAX 10005
#define MAX 99999999
#define PI 3.1415926

int witness1(int a,int m,int n)
{
	int w;
	if(m==0) return 1;
	if(m==1) return a%n;
	w=witness1(a,m/2,n);
	w=(w*w)%n;
	if(m%2==1) w=(w*a)%n;
	return w;
}

int witness2(int a,int m,int n)
{
	int x=1,y=a%m,t;
	while(m!=0)
	{
		if(m%2==1) x=(x*y)%n;
		t=y;
		y=(y*y)%n;
		if(y==1 && t!=1 && t!=n-1) return 1;
		m/=2;
	}
	if(x!=1) return 1;
	else return 0;
}

int miller_rabin(int x)
{
	int i,a;
	if(x==2) return 1;
	for(i=1;i<=5;i++)
	{
		a=x-i-1;
		if(a==0) continue;
		if(witness2(a,x-1,x)==1) return 0;
	}
	return 1;
}


int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1) printf("1 is error\n");
		else if(miller_rabin(n)==1) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}