求大牛帮忙分析这个伪素数代码哪有问题

wangyexin

#include<iostream>
#include<cmath>
using namespace std;
          
int witness(int a,int n)
{
    int x,d=1,i=ceil(log(n-1.0)/log(2.0))-1;
    for( ;i>=0;i--){
         x=d;d=(d*d)%n;
         if(d==1&&x!=1&&x!=n-1)return 1;
         if(((n-1)&(1<<i))>0)d=(d*a)%n;
    }
    return (d==1?0:1);  
}

int miller(int n,int s=100)
{
    if(n==2)return 1;
    if((n%2)==0)return 0;
    int j,a;
    for( j=0;j<s;j++){
         a=rand()*(n-2)/RAND_MAX+1;
         if(witness(a,n))return 0;
    }
    return 1;  
}



int main()
{
    int a,b; 
    while(cin>>a>>b)
    {
       for(int i=a;i<=b;i++)
       {    
            if(miller(i))  cout<<i<<endl;// 输出a到b之间的素数
       
       } 
    }
    system("pause");
    return 1;
}

linha0

伪素数？？什么来的？？

wangyexin

回复 linha0 的帖子

就是根据伪素数原理 判断一个数是不是素数