fork(3) download
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. const int M = 1e5;
  7. int L;
  8. vector<long long> primes;
  9.  
  10. long long Mul(long long a, long long n, long long m) {
  11. long long r = 0;
  12. while (n) {
  13. if (n % 2 == 1)
  14. r = (r + a) % m;
  15. a = (a + a) % m;
  16. n /= 2;
  17. }
  18. return r;
  19. }
  20.  
  21. long long Pow(long long a, long long n, long long m) {
  22. long long r = 1;
  23. while (n) {
  24. if (n % 2 == 1)
  25. r = Mul(r, a, m);
  26. a = Mul(a, a, m);
  27. n /= 2;
  28. }
  29. return r;
  30. }
  31.  
  32. bool fermat(long long n, int iter) {
  33. if (n == 1)
  34. return false;
  35. if (n <= 1e10) {
  36. for (int k = 0; k < L; k++) {
  37. if (n == primes[k])
  38. return true;
  39. if (n % primes[k] == 0)
  40. return false;
  41. }
  42. }
  43. for (int k = 0 ; k < iter; k++) {
  44. long long a = 1 + rand() % (n-1); // 1 <= a <= n-1
  45. if (Pow(a, n-1, n) != 1)
  46. return false;
  47. }
  48. return true;
  49. }
  50.  
  51. int main() {
  52. bool* A = (bool*) calloc(M+1, sizeof(bool));
  53. for (int k = 2; k <= M; k++)
  54. if (!A[k]) {
  55. primes.push_back(k);
  56. if (k * 1ll * k <= M)
  57. for (int j = k*k; j <= M; j += k)
  58. A[j] = true;
  59. }
  60. L = primes.size();
  61. long long n;
  62. int t;
  63. scanf("%d", &t);
  64. for (int k = 0; k < t; k++) {
  65. scanf("%lld", &n);
  66. if (fermat(n,3))
  67. printf("YES\n");
  68. else
  69. printf("NO\n");
  70. }
  71. return 0;
  72. }
Success #stdin #stdout 0s 3520KB
stdin
2
6
17
stdout
NO
YES