fork(3) download
copy 
  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
comments (?)
stdin
copy 
2
6
17
stdout
copy 
NO
YES
https://ideone.com/zSjc1n
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!