﻿

# UniquePrimeFactorization

Nov 26th, 2020 (edited)
672
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cmath>
2. #include <iostream>
3.
4. using namespace std;
5.
6. unsigned prime_factors(unsigned max, unsigned** factors)
7. {
8.     if (max < 2) {
9.         return -1;
10.     }
11.
12.     // find all prime factors
13.
14.     bool* is_composite = new bool[max + 1] { false };
15.     double sup = sqrt(max) + 1;
16.
17.     for (size_t i = 3; i <= sup; i += 2) {
18.         if (!is_composite[i]) {
19.             for (size_t j = 3; i * j <= max; j += 2) {
20.                 is_composite[i * j] = true;
21.             }
22.         }
23.     }
24.
25.     // calculate the number of prime factors
26.
27.     unsigned count = 1;
28.
29.     for (size_t i = 3; i <= max; i += 2) {
30.         count += !is_composite[i];
31.     }
32.
33.     // allocate space and fill in the prime factors
34.
35.     if (factors != nullptr) {
36.         *factors = new unsigned[count];
37.
38.         unsigned index = 0;
39.         (*factors)[index++] = 2;
40.
41.         for (size_t i = 3; i <= max; i += 2) {
42.             if (!is_composite[i]) {
43.                 (*factors)[index++] = i;
44.             }
45.         }
46.     }
47.
48.     delete[] is_composite;
49.     return count;
50. }
51.
52. int main(int argc, char const* argv[])
53. {
54.     unsigned* factors = nullptr;
55.     unsigned factors_cnt = prime_factors(100, &factors);
56.
57.     unsigned N;
58.     cin >> N;
59.
60.     unsigned exponents[100] = { 0 };
61.
62.     for (size_t i = 0; i < factors_cnt; i++) {
63.         while (N % factors[i] == 0) {
64.             exponents[i]++;
65.             N /= factors[i];
66.         }
67.     }
68.
69.     for (size_t i = 0; i < factors_cnt; i++) {
70.         cout << factors[i] << "\t" << exponents[i] << endl;
71.     }
72.     cout << N << endl;
73.
74.     if (factors != nullptr) {
75.         delete[] factors;
76.     }
77.
78.     return 0;
79. }
80.
RAW Paste Data