fork download
copy 
  1. #include <cstdio>
  2.  
  3. // the gretest common divisor
  4. int gcd(int a, int b) {
  5.     while (b > 0) {
  6. 		int c = a % b;
  7. 		a = b;
  8. 		b = c;
  9. 	}
  10. 	return a;
  11. }
  12.  
  13. // the maximal value for A[i]
  14. const int maxA = 100000;
  15.  
  16. // minp[x] is the minimal prime divisor of x
  17. // this array initialized by zeros since it is defined outside any function
  18. int minp[maxA + 1];
  19.  
  20. int main() {
  21. 	// we calculate minp[x] using sieve of Eratosthenes
  22. 	// in O(maxA * log(log(maxA))) time
  23. 	minp[1] = -1;
  24. 	for (int i = 2; i <= maxA; ++i) {
  25. 		if (minp[i] == 0) {
  26. 			for (int j = i; j <= maxA; j += i) {
  27. 				if (minp[j] == 0) {
  28. 					minp[j] = i;
  29. 				}
  30. 			}
  31. 		}
  32. 	}
  33.  
  34. 	int T;
  35. 	scanf("%d", &T);
  36. 	for (int t = 0; t < T; ++t) {
  37. 		int n;
  38. 		scanf("%d", &n);
  39. 		// d is gcd of all A[i]
  40. 		int d = 0;
  41. 		for (int i = 0; i < n; ++i) {
  42. 			int Ai;
  43. 			scanf("%d", &Ai);
  44. 			d = gcd(d, Ai);
  45. 		}
  46. 		int ans = minp[d];
  47. 		printf("%d\n", ans);
  48. 	}
  49. 	return 0;
  50. }
Success #stdin #stdout 0.02s 3072KB
comments (?)
stdin
copy 
1
1
24371
stdout
copy 
24371
https://ideone.com/cUdvXE
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!