Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

126378's blog

By 126378, history, 4 weeks ago, In English,

Can you give me the easy and understandable implementation of Miller Rabin in C++?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but it gives wrong output in some cases. Example: 999999999999999989 its a prime number but the output is its a composite number.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you sure? I just tried it, and MillerRabin(999999999999999989LL) returns true, indicating that it is probably prime.

      You must made an error calling the function (maybe you forgot to mark it as a long long number?).

      Also, if you want to go safe, just use the deterministic Miller-Rabin code, from the next section.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes I forgot to mark the number long long..Thank you :)