求本原元

admin

#include <stdio.h>
#include <string.h>

int y[100000] = {} ;

int sort(int n)  
{
           int cnt=0;
           for(long i=2;i*i<=n;i++) {
                   while(n%i==0) {
                           y[cnt++]=i;
                           n/=i;
                   }
           }
           if(n!=1) {//如果n是一个合数，那么它的分解素因子只可能有一个大于sqrt(n)的；
                   //原因：设d能整除n,则n=d*n/d,则min(d,n/d)<=sqrt(n)。
                   y[cnt++]=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[tmp-1];
                                        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;
}