susu.cpp

很多密码算法都要随机选择一个大素数

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


void main()
{
   int k=1,q,n,kpow,key,key2=1;
   cin>>n;
   while(k>0)
   {
	  kpow=pow(2,k); 
	  q=(n-1)/kpow;
		  if(q%2==1)
			  break;
		  ++k;
   }
   for(int a=2;a<n-1;++a)
   {
	  
	   int apowq=pow(a,q);
	   if(apowq%n==1)
	   {
		   cout<<"不确定"<<endl;
	  continue;
	   }
		 else 
		 {for(int j=0;j<k;++j)
		 { 
			  int Apow2jq=pow(a,q*pow(2,j));
			  if(Apow2jq%n==n-1)
			    key=0; 
             else key=1;
			key2=key2*key;

	  }
	
     if(key2==0)  cout<<"不确定"<<endl;
else  cout<<"合数"<<endl;
   }

   }
}