求质数方法

既然是"筛选法"，那他的核心思想就是从N个整数中逐个筛去合数，留下质数。
其原理为：

1. 初始时先准备值为 以内的所有质数
2. 依次删除 以内的上述质数的所有倍数 。
3. 最终则会留下 以内的所有质数。
4. 随后以 以内的所有质数做种，重复步骤1-4，直到找到 内所有质数。

原理优化：

1. 由于第四步 "重复步骤1-4" 时会反复筛选上一次已经筛干净的质数域，故从第二轮开始的步骤2中的 "" 无需从 开始，从 开始即可( 为上一次确定的质数范围)。

• 时间复杂度：
• 空间复杂度：

/**
 * @brief: 求range以内的所有质数
 * @param:
 *     bool *is_prime: 应传入的大小为range+1的bool数组，用于缓存结果
 *     int range:      求解质数的范围，其值应小于根号下的int值域上限(约46340)
 **/
void Eratasthene(bool *is_prime, int range)
{
	if(range < 2)
	{
		memset(is_prime, 0, (range + 1) * sizeof(bool));
		return;
	}
	// 将所有标志位置1
	memset(is_prime, 1, (range + 1) * sizeof(bool));
	// 设置2以前的质数
	is_prime[0] = false;
	is_prime[1] = false;

	// 当前可确定的质数范围
	int scope = 2;
	// 上一次确定的质数范围
	int last_scope = 2;
	while (last_scope * last_scope <= range)
	{
		for (int i = 2; i <= scope; i++)
		{
			if (is_prime[i])
			{
				// 进行质数筛
				int multiple = i * i > scope ? i : scope / i;
				int comp = multiple * i;
				while ((comp = (multiple * i)) <= range)
				{
					is_prime[comp] = false;
					multiple++;
				}
			}
		}
		last_scope = scope;
		scope = scope * scope;
	}
}
复制

• 时间复杂度：
• 空间复杂度：