Miller-Rabin SPOJ WA

Question

我想第一次實現Miller-Rabin。我的代碼給出了所有測試用例的正確答案，我試過但仍然在SPOJ上給出了錯誤的答案。 問題陳述：我應該打印 「YES」，如果輸入的數字是素數，否則 「NO」 請幫助：

問題鏈接：http://www.spoj.com/problems/PON/

CODE：

#include<stdio.h> 
#include<stdlib.h> 
#include<time.h> 
#define LL long long 
LL expo(LL a,LL b,LL c) 
{ 
    LL x=1,y=a; 
    if(b==0) 
      return 1; 
    while(b) 
    { 
      if(b%2==1) 
         x=(x*y)%c; 
      y=(y*y)%c; 
      b=b/2; 
    } 
    return x; 
} 
int main() 
{ 
    LL t,s,x,a,n,prime,temp; 
    scanf("%lld",&t); 
    srand(time(NULL)); 
    while(t--) 
    { 
       scanf("%lld",&n); 
       if(n<2) 
        puts("NO"); 
       else if(n==2) 
         puts("YES"); 
       else if(n%2==0) 
        puts("NO"); 
       else 
       { 
        s=n-1; 
        prime=1; 
        while(s%2==0) 
           s=s/2; 
        for(int i=0;i<20;i++) 
        { 
          a=rand()%(n-1)+1; 
          x=expo(a,s,n); 
          temp=s; 
          while((temp!=n-1)&&(x!=1)&&(x!=n-1)) 
          { 
                 x=(x*x)%n; 
                 temp*=2; 
          } 
          if((x!=n-1)&&(temp%2==0)) 
          { 
               prime=0; 
               break; 
          } 
        }   
        if(prime==0) 
           puts("NO"); 
        else 
         puts("YES");   
       } 
    } 
    return 0; 
    } 

Answer 1

請記住， puts將換行符字符'\n'附加到所給的字符串上。您可以嘗試使用printf。

Answer 2

我覺得你小號和d的計算是不正確：

function isStrongPseudoprime(n, a) 
    d := n - 1; s := 0 
    while d % 2 == 0 
     d := d/2; s := s + 1 
    t := powerMod(a, d, n) 
    if t == 1 return ProbablyPrime 
    while s > 0 
     if t == n - 1 return ProbablyPrime 
     t := (t * t) % n 
     s := s - 1 
    return Composite 

我討論一個essay米勒羅賓方法在我的博客。

Answer 3

由於整數溢出，你正在得到錯誤的答案，因爲你乘以2的長數不能在一個單一的長長類型中。

這裏是蟒蛇的解決方案來克服這個問題

import random 
_mrpt_num_trials = 25 # number of bases to test 

def is_probable_prime(n): 
    assert n >= 2 
    # special case 2 
    if n == 2: 
     return True 
    # ensure n is odd 
    if n % 2 == 0: 
     return False 
    # write n-1 as 2**s * d 
    # repeatedly try to divide n-1 by 2 
    s = 0 
    d = n - 1 
    while True: 
     quotient, remainder = divmod(d, 2) 
     if remainder == 1: 
      break 
     s += 1 
     d = quotient 
    assert(2 ** s * d == n - 1) 

    def try_composite(a): 
     if pow(a, d, n) == 1: 
      return False 
     for i in range(s): 
      if pow(a, 2 ** i * d, n) == n - 1: 
       return False 
     return True 

    for _ in range(_mrpt_num_trials): 
     a = random.randrange(2, n) 
     if try_composite(a): 
      return False 

    return True 

for i in range(int(input())): 
    a = int(input()) 
    if is_probable_prime(a): 
     print("YES") 
    else: 
     print("NO")