﻿

# PrimeFactorizeDictionaryOrder

Nov 27th, 2020
622
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.  *
3.  * 根据唯一分解定理，每个正整数n都可以唯一的表示为 n=2q03q15q2…piqi…
4.  * 其中pi是第i小的质数，qi是pi的指数（>=0）。
5.  * 也就是说每一个正整数n可以唯一的对应到一个数列q0,q1,…,qi,…。
6.  * 给定一个数组a0,a1,…,am−1，请把数组按照每个数对应的数列的字典序排序。
7.  *
8.  */
9.
10. #include <cmath>
11. #include <cstring>
12. #include <iostream>
13.
14. unsigned primes(unsigned max, unsigned** factors)
15. {
16.     if (max < 2) {
17.         return -1;
18.     }
19.
20.     // find all prime factors
21.
22.     bool* is_composite = new bool[max + 1] { false };
23.     double sup = sqrt(max) + 1;
24.
25.     for (size_t i = 3; i <= sup; i += 2) {
26.         if (!is_composite[i]) {
27.             for (size_t j = 3; i * j <= max; j += 2) {
28.                 is_composite[i * j] = true;
29.             }
30.         }
31.     }
32.
33.     // calculate the number of prime factors
34.
35.     unsigned count = 1;
36.
37.     for (size_t i = 3; i <= max; i += 2) {
38.         count += !is_composite[i];
39.     }
40.
41.     // allocate space and fill in the prime factors
42.
43.     if (factors != nullptr) {
44.         *factors = new unsigned[count];
45.
46.         unsigned index = 0;
47.         (*factors)[index++] = 2;
48.
49.         for (size_t i = 3; i <= max; i += 2) {
50.             if (!is_composite[i]) {
51.                 (*factors)[index++] = i;
52.             }
53.         }
54.     }
55.
56.     delete[] is_composite;
57.     return count;
58. }
59.
60. void prime_factorize(unsigned n, unsigned* primes, unsigned prime_cnt, unsigned* exponents)
61. {
62.     memset(exponents, 0, prime_cnt * sizeof(unsigned));
63.
64.     for (size_t i = 0; i < prime_cnt; i++) {
65.         while (n % primes[i] == 0) {
66.             exponents[i]++;
67.             n /= primes[i];
68.         }
69.     }
70. }
71.
72. bool gt(unsigned* arr1, unsigned* arr2, unsigned cnt)
73. {
74.     if (cnt == 0) {
75.         return false;
76.     }
77.
78.     if (*arr1 > *arr2) {
79.         return true;
80.     } else if (*arr1 < *arr2) {
81.         return false;
82.     } else {
83.         return gt(arr1 + 1, arr2 + 1, cnt - 1);
84.     }
85. }
86.
87. template <class T>
88. void swap(T& a, T& b)
89. {
90.     T tmp = b;
91.     b = a;
92.     a = tmp;
93. }
94.
95. void sort(unsigned* index, unsigned** aoa, unsigned row, unsigned col)
96. {
97.     for (size_t i = 0; i < row; i++) {
98.         for (size_t j = i + 1; j < row; j++) {
99.             if (gt(aoa[i], aoa[j], col)) {
100.                 swap(aoa[i], aoa[j]);
101.                 swap(index[i], index[j]);
102.             }
103.         }
104.     }
105. }
106.
107. int main(int argc, char const* argv[])
108. {
109.     unsigned* factors = nullptr;
110.     unsigned factors_cnt = primes(100, &factors);
111.
112.     unsigned N;
113.     std::cin >> N;
114.
115.     unsigned* numbers = new unsigned[N];
116.     unsigned** exponent_matrix = new unsigned* [factors_cnt] { nullptr };
117.
118.     for (size_t i = 0; i < N; i++) {
119.         std::cin >> numbers[i];
120.         exponent_matrix[i] = new unsigned[factors_cnt];
121.         prime_factorize(numbers[i], factors, factors_cnt, exponent_matrix[i]);
122.     }
123.
124.     sort(numbers, exponent_matrix, N, factors_cnt);
125.
126.     for (size_t i = 0; i < N; i++) {
127.         std::cout << numbers[i] << " ";
128.     }
129.     std::cout << std::endl;
130.
131.     if (factors != nullptr) {
132.         delete[] factors;
133.     }
134.
135.     delete[] numbers;
136.
137.     for (size_t i = 0; i < N; i++) {
138.         delete[] exponent_matrix[i];
139.     }
140.
141.     delete[] exponent_matrix;
142.
143.     return 0;
144. }
145.
RAW Paste Data