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

wangyexin

1. 
   
2. #include<iostream>
   
3. #include<cmath>
   
4. using namespace std;
   
5.          
   
6. int witness(int a,int n)
   
7. {
   
8.     int x,d=1,i=ceil(log(n-1.0)/log(2.0))-1;
   
9.     for( ;i>=0;i--){
   
10.          x=d;d=(d*d)%n;
    
11.          if(d==1&&x!=1&&x!=n-1)return 1;
    
12.          if(((n-1)&(1<<i))>0)d=(d*a)%n;
    
13.     }
    
14.     return (d==1?0:1);  
    
15. }
    
16. 
    
17. int miller(int n,int s=100)
    
18. {
    
19.     if(n==2)return 1;
    
20.     if((n%2)==0)return 0;
    
21.     int j,a;
    
22.     for( j=0;j<s;j++){
    
23.          a=rand()*(n-2)/RAND_MAX+1;
    
24.          if(witness(a,n))return 0;
    
25.     }
    
26.     return 1;  
    
27. }
    
28. 
    
29. 
    
30. 
    
31. int main()
    
32. {
    
33.     int a,b;
    
34.     while(cin>>a>>b)
    
35.     {
    
36.        for(int i=a;i<=b;i++)
    
37.        {   
    
38.             if(miller(i))  cout<<i<<endl;// 输出a到b之间的素数
    
39.       
    
40.        }
    
41.     }
    
42.     system("pause");
    
43.     return 1;
    
44. }
    

复制代码

linha0

伪素数？？什么来的？？

wangyexin

回复 linha0 的帖子

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