Visual C++ - Getting Prime Factors of a Number
Given a number, we can find out what would be the prime factors of the number. But it is not easy to find out since we have to go through couple of iteratons.
Prime Factor For 9360 = 13 * 5 * 3 * 3 * 2 * 2 * 2 * 2
Note that all the numbers 13, 5, 3, 2 are prime numbers.
Source Code
#include <stdio.h>
#include <tchar.h>
#include <iostream>
#define MAX_SIZE 15000
bool IsPrimeNumber(int num)
{
bool bPrime = true;
int factor = num / 2;
for(int i = 2; i <= factor; i++)
{
if( (num % i) == 0)
bPrime = false;
}
return bPrime;
}
int GeneratePrimeNumbers(int max, int *arr)
{
int idx = 0;
for(int i = 2; i <= max; i++)
{
if(IsPrimeNumber(i) == true)
arr[idx++] = i;
}
return idx;
}
int GetPrimeFactors(int num, int *arrResult)
{
int idx = 0;
int arr[MAX_SIZE];
while(1)
{
if(IsPrimeNumber(num) == true)
{
arrResult[idx++] = num;
return idx;
}
int count = GeneratePrimeNumbers(num, arr);
for(int i = count - 1; i >= 0; i--)
{
if( (num % arr[i]) == 0)
{
arrResult[idx++] = arr[i];
num = num / arr[i];
break;
}
}
}
return idx;
}
int main()
{
int arr1[MAX_SIZE];
int num1;
std::cout << "Enter a Number: ";
std::cin >> num1;
int count = GetPrimeFactors(num1, arr1);
std::cout << "\nPrime Factors For " << num1 << " =";
for(int i = 0; i < count; i++)
{
std::cout << " " << arr1[i];
if(i != count - 1)
std::cout << " * ";
}
std::cout << "\n\n";
return 0;
}
Output
Enter a Number: 9360
Prime Factors For 9360 = 13 * 5 * 3 * 3 * 2 * 2 * 2 * 2
Press any key to continue . . .
Enter a Number: 48125
Prime Factors For 48125 = 11 * 7 * 5 * 5 * 5 * 5
Press any key to continue . . .
|
|