求本原元
#include <stdio.h>#include <string.h>
int y = {} ;
int sort(int n)
{
int cnt=0;
for(long i=2;i*i<=n;i++) {
while(n%i==0) {
y=i;
n/=i;
}
}
if(n!=1) {//如果n是一个合数，那么它的分解素因子只可能有一个大于sqrt(n)的；
//原因：设d能整除n,则n=d*n/d,则min(d,n/d)<=sqrt(n)。
y=n;
}
return cnt;
}
unsigned int fast_pow ( unsigned long x, unsigned long y, unsigned long m ){
unsigned long temp;
if ( y == 1 )
return x;
else if ( (unsigned long)y % 2 == 0 ) {
temp = fast_pow(x,y/2,m); // 用临时变量减少重复的运算
return (temp*temp)%m;
}
else {
temp = fast_pow(x,(y-1)/2,m);
return (((temp*temp)%m)*x)%m;
}
}
int main()
{
// printf("输入两个数，判断两个数之间的素数\n");
// int num1 = 16718909, num2=16718909, count = 0;
//int num1 = 16718909, num2=16726971, count = 0;
int num1 = 16718909, num2=16776971, count = 0;
// scanf("%d %d",&num1,&num2);
int foundbenyuan = 0;
printf("素数分别为：\n");
for (int i=num1;i<=num2;i++)
{
int bian = 2;
for (int j = 2; j < num2; j++)
{
if (i % j == 0 && i != j)
{
//printf("它不是素数%d\n",i);
bian = 1;
break;
}
}
if(bian==2)
{
printf("\n%d ",i);
int b = sort(i - 1);
// printf("\nyinzi %d个\n",b);
for (int a = 112;a <= 127;a ++)
{
foundbenyuan = 1;
for(int tmp = b;tmp;tmp--)
{
int q = y;
int p = (i - 1)/q;
int c = fast_pow(a,p,i);
// printf("q:%d ",fast_pow(a,i-1,i));
if((a%=i) == 1)
{
foundbenyuan = 0;
break;
}
}
if(foundbenyuan)
printf("<%d>",a);
}
count++;
if(!(count%8))
printf("\n");
}
}
printf("\n素数共有%d个\n",count);
return 0;
}
页:
[1]