fbpx

C++: Factors of an Integer

Bjarne-stroustrup
 

Compute the factors of a positive integer. These factors are the positive integers by which the number being factored can be divided to yield a positive integer result (though the concepts function correctly for zero and negative integers, the set of factors of zero has countably infinite members, and the factors of negative integers can be obtained from the factors of related positive numbers without difficulty; this task does not require handling of either of these cases). Note that even prime numbers will have at least two factors; ‘1’ and themselves.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

std::vector<int> GenerateFactors(int n)
{
	std::vector<int> factors;
	factors.push_back(1);
	factors.push_back(n);
	for(int i = 2; i * i <= n; ++i)
	{
		if(n % i == 0)
		{
			factors.push_back(i);
			if(i * i != n)
			factors.push_back(n / i);
		}
	}

	std::sort(factors.begin(), factors.end());
	return factors;
}

int main()
{
	const int SampleNumbers[] = {3135, 45, 60, 81};

	for(size_t i = 0; i < sizeof(SampleNumbers) / sizeof(int); ++i)
	{
		std::vector<int> factors = GenerateFactors(SampleNumbers[i]);
		std::cout << "Factors of " << SampleNumbers[i] << " are:\n";
		std::copy(factors.begin(), factors.end(), std::ostream_iterator<int>(std::cout, "\n"));
		std::cout << std::endl;
	}
}

SOURCE

Content is available under GNU Free Documentation License 1.2.