Taraxacum

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