fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int p;
  5.  
  6. int power(int x, int n) {
  7. 	int y;
  8. 	if (n == 1) return x;
  9. 	else {
  10. 		if(n%2 == 0) {
  11. 			y = power(x, n/2) % p;
  12. 			return (y * y) % p;
  13. 		}
  14. 		else {
  15. 			y = power(x, n/2) % p;
  16. 			return (((x * y) % p) * y) % p;
  17. 		}
  18. 	}
  19. }
  20.  
  21. bool divisible(int x, int n) { //determines if (x^n) - 1 is divisible by p;
  22. 	int rem = power(x, n);
  23. 	if (rem == 1) {
  24. 		return true;
  25. 	}
  26. 	else {
  27. 		return false;
  28. 	}
  29. }
  30.  
  31. int main() {
  32. 	cin >> p;
  33. 	int counter = 0;
  34. 	int primRoot;
  35. 	for (int x = 2; x < p; x++) {
  36. 		primRoot = 1;
  37. 		if(divisible(x,p-1)) {
  38. 			for (int j = 1; j < p-1; j++) {
  39. 				if(divisible(x, j)) {
  40. 					primRoot = 0;
  41. 					break;
  42. 				}
  43. 			}
  44. 			counter += primRoot;
  45. 		}
  46. 	}
  47. 	cout << counter;
  48. 	return 0;
  49. }
Success #stdin #stdout 0.37s 5512KB
comments (?)
stdin
copy 
1999
stdout
copy 
648
https://ideone.com/1HwK1C
language:
C++ (gcc 8.3)
created:
2 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!