fork download
copy 
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <math.h>
  5.  
  6. // Нахождение GCD
  7. long long gcd(long long a, long long b){
  8. 	if(b == 0)
  9. 		return a;
  10. 	return gcd(b, a % b);
  11. }
  12.  
  13. // Двоичное умножение по модулю для защиты от переполнений
  14. long long mul(long long a, long long b, long long m){
  15. 	if(b == 1)
  16. 		return a;
  17. 	if(b % 2 == 0){
  18. 		long long t = mul(a, b/2, m);
  19. 		return (2 * t) % m;
  20. 	}
  21. 	return (mul(a, b - 1, m) + a) % m;
  22. }
  23.  
  24. // Возведение в степень по модулю
  25. long long modpow (long long a, long long b, long long m){
  26. 	if(b==0)
  27. 		return 1;
  28. 	if(b % 2 == 0){
  29. 		long long t = modpow (a, b/2, m);
  30. 		return mul(t, t, m) % m;
  31. 	}
  32. 	return (mul(modpow (a, b - 1, m), a, m)) % m;
  33. }
  34.  
  35. int jacobi (int nominator, int denominator)
  36. {
  37.     int s = 0;
  38.     int remainder, power_of_two, t;
  39.     do{
  40.         remainder = nominator % denominator;
  41.         power_of_two = t = 0;
  42.         while(remainder % 2 == 0)
  43.         {
  44.             power_of_two++; 
  45.             remainder >>= 1;
  46.         }
  47.         t = remainder;
  48.         s = (s + power_of_two * (denominator * denominator - 1) / 8 + (t - 1) * (denominator - 1) / 4) % 2;
  49.         if(t == 1)
  50.             return (s) ? -1 : 1;
  51.         nominator = denominator;
  52.         denominator = t;
  53.     }while(t >= 3);
  54. }
  55.  
  56. int main(int argc, char* argv[])
  57. {
  58. 	long n;		/*n > 2, нечетное натуральное число, которое необходимо проверить на простоту*/
  59. 	long k;		/* параметр, определяющий точность теста */
  60. 	long a;
  61. 	long residue;
  62. 	double t;
  63. 	int flag = 0;
  64.  
  65. 	std::cin >> n;
  66. 	std::cin >> k;
  67.     t = 1 - 1 / pow(2.0, k);
  68.  
  69. 	srand(time(NULL));
  70.  
  71. 	for (int i=1; i <= k; i++)
  72. 	{
  73. 		a = rand() % (n - 2) + 2;
  74. 		long long p = modpow(a, (n - 1) / 2, n);
  75. 		int j = jacobi (a, n);
  76. 		residue = p - n;
  77.  
  78. 		if (gcd(a, n) != 1)
  79. 		{
  80. 			flag = 1;
  81. 			break;
  82. 		}
  83. 		else if (p != j)
  84. 		{
  85. 			std::cout << "[DEBUG]: p - n = " << (p - n) << std::endl;
  86. 			std::cout << "[DEBUG]: residue = " << residue << std::endl;
  87. 			std::cout << "[DEBUG]: modpow = " << p << std::endl;
  88. 			std::cout << "[DEBUG]: jacobi = " << j << std::endl;
  89. 			flag = 2;
  90. 			break;
  91. 		}
  92. 	}
  93.  
  94.  
  95. 	if (flag !=0)
  96. 	{
  97. 		std::cout << "composite \n";
  98. 	}
  99. 	else
  100. 		std::cout<<"prime with possibility " << t << "\n";                                        
  101.     return 0;
  102. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
311 10
stdout
copy 
[DEBUG]: p - n = -1
[DEBUG]: residue = -1
[DEBUG]: modpow = 310
[DEBUG]: jacobi = -1
composite
https://ideone.com/6iGauf
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!