首页 > 代码库 > MillerRabin素性测试(数论:素数Template)

MillerRabin素性测试(数论:素数Template)

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define random(a , b) ((a) + rand() % ((b) - (a) + 1)) 5 LL QuickPower(LL a , LL b , LL p) 6 { 7     LL yaoyuan = 1; 8     while(b) 9     {10         if(b & 1)   yaoyuan = yaoyuan * a % p;11         a = a * a % p;12         b >>= 1;13     }14     return yaoyuan;15 }16 bool MillerRabin(LL p)17 {18     for(int i = 1 ; i <= 50 ; ++i)19     {20         LL a = random(1 , p - 1);21         if(QuickPower(a , p - 1 , p) != 1)22         {23             return 0;24         }25     }26     return 1;27 }28 int main()29 {30     LL p = 0;31     int t;32     scanf("%d" , &t);33     while(t--)34     {35         scanf("%lld" , &p);36         if(MillerRabin(p))37         {38             printf("Yes\n");39         }40         else41         {42             printf("No\n");43         }44     }45 }

 

MillerRabin素性测试(数论:素数Template)