Prime Factors calculator in C++

Hey all, I wrote a C++ object that gets the prime factors of any number and thought I would share it.

The comments should help you and the variables have very clear names, so it should be self-documenting.

PrimeFactorsOfCalculator.h

#pragma once

#include <vector>

using namespace std;

class PrimeFactorsOfCalculator
{
public:
	PrimeFactorsOfCalculator(void);
	~PrimeFactorsOfCalculator(void);

	long GetNumber();
	void SetNumber(long inNumber);
	vector<int> GetPrimeFactors(bool inAllowDuplicates = false, bool inForceRecalculate = false);


private:
	long Number;
	vector<int> PrimeFactors;
	bool IsPrime(long inNumber);

	long MultiplyPrimes();

};

PrimeFactorsOfCalculator.cpp

#include "PrimeFactorsOfCalculator.h"
#include <math.h>
#include <algorithm>

using namespace std;

PrimeFactorsOfCalculator::PrimeFactorsOfCalculator(void)
{
}


PrimeFactorsOfCalculator::~PrimeFactorsOfCalculator(void)
{
}

long PrimeFactorsOfCalculator::GetNumber()
{
	return Number;
}

void PrimeFactorsOfCalculator::SetNumber(long inNumber)
{
	Number = inNumber;
	PrimeFactors.clear();
}

//
// Gets the prime factors of Number. 100 return 2,5.
//	
// inAllowDuplicates - Allow duplicates, for example, 100 has prime 
// factors of 2 and 5,but in order to get 100, you need 2*2*5*5. So 
// instead of returning 2,5 the return array will be 2,2,5,5.
//
// inForceRecalculate - By default the values are stored at first
// calculation and only recalcuated when needed. this is for efficiency.
vector<int> PrimeFactorsOfCalculator::GetPrimeFactors(bool inAllowDuplicates, bool inForceRecalculate)
{
	// Don't recalculate if already calculated.
	if (PrimeFactors.size() > 0 && !inForceRecalculate)
		return PrimeFactors;

	PrimeFactors.clear();
	// Calculate
	if (Number % 2 == 0 && Number >= 2)
	{
		PrimeFactors.push_back(2);
	} 

	for (int i = 3; i < Number/3; i++)
	{
		if (Number % i == 0 && IsPrime(i))
			PrimeFactors.push_back(i);
	}

	// Allow duplicates, for example, 100 has prime factors of 2 and 5,
	// but in order to get 100, you need 2*2*5*5. So instead of returning
	// 2,5 the return array will be 2,2,5,5.
	if (inAllowDuplicates)
	{
		while (MultiplyPrimes() != Number)
		{
			long multipliedVal = MultiplyPrimes();
			long val = 0;

			if (multipliedVal != 0)
				val = Number / multipliedVal;

			if (IsPrime(val))
			{
				PrimeFactors.push_back(val);
				continue;
			}
			else
			{
				// recursion
				PrimeFactorsOfCalculator calc = PrimeFactorsOfCalculator();
				calc.SetNumber(val);
				vector<int> duplicateFactors = calc.GetPrimeFactors();
				for (size_t i = 0; i < duplicateFactors.size(); i++)
				{
					PrimeFactors.push_back(duplicateFactors.at(i));
				}
			}
		}
	}

	sort(PrimeFactors.begin(), PrimeFactors.end());
	return PrimeFactors;
}

bool PrimeFactorsOfCalculator::IsPrime(long inNumber)
{
	// Get square root as that is the highest possible factor
	// and add one in case precision is screwy.
	long highestPossibleFactor = (long)(sqrt((double)inNumber) + 1);

	// Handle 2 separatly then no other even has to be checked
	if (inNumber % 2 == 0) 
		return false;

	// See if the value is divisible by any odd number
	// if so it is not prime
	for (int i = 3; i < highestPossibleFactor; i+=2)
	{
		if (inNumber % i == 0) 
			return false;
	}
	return true;
}

long PrimeFactorsOfCalculator::MultiplyPrimes()
{
	if (PrimeFactors.size() == 1)
		return PrimeFactors.at(0);
	else if (PrimeFactors.size() > 1)
	{
		int minVal = PrimeFactors.at(0);
		for (size_t i = 1; i < PrimeFactors.size(); i++)
		{
			minVal *= PrimeFactors.at(i);
		}
		return minVal;
	}
	else return 1; // 1 is always a prime
}

And last here is a sample main function that uses this.

Main.cpp

#include <vector>
#include "PrimeFactorsOfCalculator.h"

using namespace std;

int main()
{
	PrimeFactorsOfCalculator calc = PrimeFactorsOfCalculator();
	calc.SetNumber(100);
	vector<int> primeFactors = calc.GetPrimeFactors();
	vector<int> primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);


	calc.SetNumber(200);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);


	calc.SetNumber(1000);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);

	calc.SetNumber(14593);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);

	calc.SetNumber(12345678);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);
}

Leave a Reply

How to post code in comments?