Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cmath> // sqrt()
- using namespace std;
- // This program displays the specified positive integer as
- // the product of its prime factors.
- // The integer must be in the range 2 - 2147483647
- void display_prime_factors(int integer)
- {
- // The integer is a sequence of prime numbers, some
- // are repeated, some are not.
- int factor_count = 0; // Count the occurence of each factor.
- bool factor_found = false; // No factor has been found yet. (This is for formatting.)
- // First count the number of factors of 2
- while (integer % 2 == 0) // If the integer is divisible by 2,
- {
- factor_count++; // Count one factor of 2.
- integer /= 2; // Remove that factor from the integer.
- }
- if (factor_count) factor_found = true; // If a factor was found, indicate it.
- // If there were more than one factors of two,
- // display 2 with exponent notation and the number of occurences,
- // then a multiplication sign for the next factor.
- if (factor_count > 1)
- {
- cout << "2^" << factor_count;
- }
- // If there was only one factor of 2, just display the 2.
- else if (factor_count == 1)
- {
- cout << "2";
- }
- // Now that all the factors of 2 are removed from the integer,
- // the rest of the factors in the remaining integer must be odd numbers.
- // We only need to check for all odd numbers less than or equal to the square
- // root of the integer, because the "greater than" side of the square root
- // has all the same factors as the "less than" side.
- for (int i = 3; i <= sqrt(integer); i += 2) // For odd numbers less than or equal to the square root
- {
- factor_count = 0; // Reset the factor count.
- while (integer % i == 0) // If the integer is divisible by the current odd number,
- {
- factor_count++; // Count that odd number as a factor.
- integer /= i; // Remove the factor from the integer.
- }
- // If there is a new odd factor and this is not the first
- // factor found, we need a multiplication sign in front.
- if (factor_count && factor_found) cout << " * ";
- // If there is a new odd factor and this is the first factor found,
- // indicate a factor was found (needed for future formatting).
- if (factor_count && !factor_found) factor_found = true;
- // If the factor occurs more than once, use exponent notation.
- if (factor_count > 1)
- {
- cout << i << "^" << factor_count;
- }
- // If there was only one occurence of the odd number, display the number.
- else if (factor_count == 1)
- {
- cout << i;
- }
- }
- // If the remaining integer is greater than one, it means
- // it is a prime number.
- if (integer > 1)
- {
- if (factor_found) cout << " * "; // If there's a factor before it, add a multiplication sign
- cout << integer << "\n";
- }
- cout << "\n"; // Go to the next line.
- }
- int main() {
- int number = 0; // The number to break into prime factors.
- cout << "This program expresses a positive integer as\n"
- "a product of prime factors.\n\n";
- cout << "Enter an integer : ";
- cin >> number; // Get the user's number.
- while ((number < 2) || (number > 2147483647)) // If the user's input is not within the range of an int,
- {
- cout << "Please enter a number in the range of 2 - 2147483647\n\n";
- cout << "Enter an integer : ";
- cin >> number; // Get new input.
- }
- cout << number << " =\n"; // Announce the result.
- display_prime_factors(number); // Display the result.
- cout << "\n"; // Go to the next line.
- return 0; // End the program.
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement