fermat.cpp

来自「实现素性检测。但不能实现太大的数」· C++ 代码 · 共 40 行

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(void)
{
    int i,j,a,b,c,n,m=0;
	int r=1;
	printf("请输入给定的奇数：\n");
	scanf("%d",&a);
	if(a%2==0)
	{printf("请重新输入一个奇数:\n");
	   scanf("%d",&c);
	   a=c;}
	printf("请输入给定的安全参数：\n");
    scanf("%d",&b);
	for(j=0;j<=b;j++)
	{ time_t t;
     srand((unsigned) time(&t));
    //printf("Ten random numbers from 0 to 99\n");
    //for(i=0; i<10; i++)
	//do
	n=rand() % (a-2);
    
//	while(n!=0||n!=1);
//	printf("%d\n", n);
	for(i=1;i<=a-1;i++)
		r=(r*n)%a;
	if(r!=1)
       // m++;
	//	printf("%d可能为素数。\n",a);
//	else
	{printf("%d为合数。\n",a);
	 break;
	}
	else
		m++;
	}
	if(m!=0)
   printf("%d可能为素数。\n",a);
}