求解自然数的因数

之前室友问了我一个题目，怎么求一个自然数的所有因数（升序排列）。

我很快想到了一个时间复杂度 O(n) 的简单实现。

std::vector<size_t> get_factors(size_t N)
{
	using std::vector;
	if (N <= 1)
	{
		return vector<size_t>(1, N);
	}
	std::vector<size_t> factors;
	size_t t = N >> 1;
	for (size_t i = 2; i <= t; ++i)
	{
		if (N % i == 0)
		{
			factors.emplace_back(i);
		}
	}
	return factors;
}

这个算法效率较低，闲来无事，我感觉这个问题蛮常见的，就想了想优化一下。

比较容易想到质因数分解，为了效率，我先实现了一个简单的函数，把 [1, n] 的质数输出到文件中保存起来。

size_t generate_prime(const size_t N, const char* path = "prime.txt")
{
	using std::ofstream;
	using std::vector;
	ofstream f(path, std::ofstream::ate);
	size_t cnt = 0;
	if (!f.is_open())
	{
		return cnt;
	}
	vector<size_t> V(N + 1, 0);
	for (size_t i = 2; i <= N; ++i)
	{
		if (V[i] == 0)
		{
			for (size_t j = i * i; j <= N; j += i)
			{
				V[j] = 1;
			}
			f << i << ',';
			++cnt;
		}
	}
	f.close();
	return cnt;
}

然后在需要的时候把质数拿出来，这个过程只需要在最开始执行一次。

std::vector<size_t> read_prime(const size_t N, const char* path = "prime.txt")
{
	using std::ifstream;
	using std::string;
	using std::getline;
	using std::vector;
	vector<size_t> prime(N);
	ifstream f(path, std::ifstream::in);
	if (!f.is_open())
	{
		return prime;
	}
	string buf;
	size_t cur = 0, next = 0, str_len = 0, cnt = 0;
	while (!f.eof())
	{
		getline(f, buf);
		str_len = buf.length();
		while (cur < str_len && cnt < N)
		{
			next = buf.find(',', cur);
			for (size_t i = cur; i < next; ++i)
			{
				prime[cnt] *= 10;
				prime[cnt] += buf[i] - '0';
			}
			++cnt;
			cur = next + 1;
		}
	}
	return prime;
}

把质素数组引用作为参数传入函数补助质因数分解。

每次分解质因数后，与之前的数据相乘放入到临时集合中，每次迭代后再与之前的质因数集合合并。

返回时转为 vector 方便后续操作。

  • 这里用集合是为了防止元素重复。也有其他办法，但这是我认为最方便快捷的，考虑到一个数如果不是特别大，因数也不会特别多，使用集合的效率是可以保证的。
  • 集合里面的元素默认按照 key 值升序排列。
// Please make sure that prime array is enough.
std::vector<size_t> get_factors(size_t N, std::vector<size_t>& prime)
{
	using std::set;
	using std::vector;
	set<size_t> factors;
	if (N <= 1)
	{
		return vector<size_t>(1, N);
	}
	size_t cur = prime[0], idx = 0;
	while (N > 1)
	{
		while (N % cur == 0)
		{
			N /= cur;
			set<size_t> _tmp{cur};
			for (auto&& it : factors)
			{
				_tmp.insert(cur * it);
			}
			factors.insert(_tmp.begin(), _tmp.end());
		}
		cur = prime[idx++];
	}
	return vector<size_t>{factors.begin(), factors.end()};
}

测试结果。

[1, 10000]（2倍）

time of using prime: 0.057 s

time of no prime: 0.105 s

[1, 100000]（10倍）

time of using prime: 0.96 s

time of no prime: 9.615 s

[1, 1000000]（30倍）

time of using prime: 29.06 s

time of no prime: 947.528 s

测试代码。

void test()
{
	using std::cout;
	using std::endl;

	auto prime{ read_prime(generate_prime(1000010)) };

	time_t cb1 = clock();
	for (size_t i = 1; i <= 100000; ++i)
	{
		auto r = get_factors(i, prime);
	}
	time_t ce1 = clock();
	cout << "time of using prime: " << (double)(ce1 - cb1) / CLOCKS_PER_SEC  << " s" << endl;

	time_t cb2 = clock();
	for (size_t i = 1; i <= 100000; ++i)
	{
		auto r = get_factors(i);
	}
	time_t ce2 = clock();
	cout << "time of no prime: " << (double)(ce2 - cb2) / CLOCKS_PER_SEC << " s" << endl;
}