fork(3) download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3.  
  4. #define FACTOR_LIM (int) 1e6+2 // used by preFactor(n). Defined as <= n <= 1e8
  5.  
  6. using namespace std;
  7.  
  8. int lowestDiv[FACTOR_LIM+1], a[FACTOR_LIM], c[FACTOR_LIM], n;
  9. int o[FACTOR_LIM][21];
  10.  
  11. void preFactor(int n) {
  12. 	int root = 2;
  13. 	for(int i = 2; i*i <= n; i++) {
  14. 		if(lowestDiv[i]) continue;
  15. 		root = lowestDiv[i] = i;
  16. 		for(int j = i*i; j <= n; j+=i) {
  17. 			lowestDiv[j] = (lowestDiv[j]) ? lowestDiv[j] : i;
  18. 		}
  19. 	}
  20. 	for(int i = root; i <= n; i++) {
  21. 		if(!lowestDiv[i]) {
  22. 			lowestDiv[i] = i;
  23. 		}
  24. 	}
  25. }
  26.  
  27. void fastFactor(int n, int i) {
  28. 	int j = 0;
  29. 	while(n > 1) {
  30. 		o[i][j++] = (lowestDiv[n]);
  31. 		n /= lowestDiv[n];
  32. 	}
  33. 	if(n > 1) o[i][j++] = n;
  34. }
  35.  
  36. bool cmp(const int i, const int j) {
  37. 	int vi = 0, vj = 0;
  38. 	while(o[i][vi] != 0 && o[j][vj] != 0) {
  39. 		if(o[i][vi] < o[j][vj]) return true;
  40. 		else if(o[i][vi] > o[j][vj]) return false;
  41. 		vi++;
  42. 		vj++;
  43. 	}
  44. 	return o[j][vj];
  45. }
  46.  
  47. int main() {
  48. 	preFactor(FACTOR_LIM-1);
  49. 	scanf("%d",&n);
  50.  
  51. 	for(int i = 0; i < n; i++) {
  52. 		scanf("%d",&a[i]);
  53. 		fastFactor(a[i], i);
  54. 		c[i] = i;
  55. 	}
  56. 	sort(c,c+n,cmp);
  57.  
  58. 	for(int i = 0; i < n; i++) {
  59. 		printf("%d\n",a[c[i]]);
  60. 	}
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 148032KB
comments (?)
stdin
copy 
5
2 3 4 5 6
stdout
copy 
2
4
6
3
5
https://ideone.com/OjlO5i
language:
C++14 (gcc 8.3)
created:
6 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!