Advertisement
janac

Prime factorization

Dec 21st, 2021
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.77 KB | None | 0 0
  1. #include<iostream>
  2. #include<cmath> // sqrt()
  3. using namespace std;
  4.  
  5. // This program displays the specified positive integer as
  6. // the product of its prime factors.
  7. // The integer must be in the range 2 - 2147483647
  8. void display_prime_factors(int integer)
  9. {
  10.     // The integer is a sequence of prime numbers, some
  11.     // are repeated, some are not.
  12.     int factor_count = 0; // Count the occurence of each factor.
  13.  
  14.     bool factor_found = false; // No factor has been found yet. (This is for formatting.)
  15.  
  16.     // First count the number of factors of 2
  17.     while (integer % 2 == 0) // If the integer is divisible by 2,
  18.     {
  19.         factor_count++; // Count one factor of 2.
  20.         integer /= 2; // Remove that factor from the integer.
  21.     }
  22.  
  23.     if (factor_count) factor_found = true; // If a factor was found, indicate it.
  24.  
  25.     // If there were more than one factors of two,
  26.     // display 2 with exponent notation and the number of occurences,
  27.     // then a multiplication sign for the next factor.
  28.     if (factor_count > 1)
  29.     {
  30.         cout << "2^" << factor_count;
  31.     }
  32.        
  33.     // If there was only one factor of 2, just display the 2.
  34.     else if (factor_count == 1)
  35.     {
  36.         cout << "2";
  37.     }
  38.  
  39.     // Now that all the factors of 2 are removed from the integer,
  40.     // the rest of the factors in the remaining integer must be odd numbers.
  41.     // We only need to check for all odd numbers less than or equal to the square
  42.     // root of the integer, because the "greater than" side of the square root
  43.     // has all the same factors as the "less than" side.
  44.     for (int i = 3; i <= sqrt(integer); i += 2) // For odd numbers less than or equal to the square root
  45.     {
  46.         factor_count = 0; // Reset the factor count.
  47.         while (integer % i == 0) // If the integer is divisible by the current odd number,
  48.         {
  49.             factor_count++; // Count that odd number as a factor.
  50.             integer /= i; // Remove the factor from the integer.
  51.         }
  52.         // If there is a new odd factor and this is not the first
  53.         // factor found, we need a multiplication sign in front.
  54.         if (factor_count && factor_found) cout << " * ";
  55.         // If there is a new odd factor and this is the first factor found,
  56.         // indicate a factor was found (needed for future formatting).
  57.         if (factor_count && !factor_found) factor_found = true;
  58.         // If the factor occurs more than once, use exponent notation.
  59.         if (factor_count > 1)
  60.         {
  61.            cout << i << "^" << factor_count;
  62.         }
  63.            
  64.         // If there was only one occurence of the odd number, display the number.
  65.         else if (factor_count == 1)
  66.         {
  67.             cout << i;
  68.         }
  69.     }
  70.  
  71.     // If the remaining integer is greater than one, it means
  72.     // it is a prime number.
  73.     if (integer > 1)
  74.     {
  75.         if (factor_found) cout << " * "; // If there's a factor before it, add a multiplication sign
  76.         cout << integer << "\n";
  77.     }
  78.     cout << "\n"; // Go to the next line.
  79. }
  80.  
  81. int main() {
  82.  
  83.     int number = 0; // The number to break into prime factors.
  84.     cout << "This program expresses a positive integer as\n"
  85.         "a product of prime factors.\n\n";
  86.     cout << "Enter an integer : ";
  87.     cin >> number; // Get the user's number.
  88.     while ((number < 2) || (number > 2147483647)) // If the user's input is not within the range of an int,
  89.     {
  90.         cout << "Please enter a number in the range of 2 - 2147483647\n\n";
  91.         cout << "Enter an integer : ";
  92.         cin >> number; // Get new input.
  93.     }
  94.  
  95.     cout << number <<  " =\n"; // Announce the result.
  96.     display_prime_factors(number); // Display the result.
  97.     cout << "\n"; // Go to the next line.
  98.     return 0; // End the program.
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement