求1~n之间的素数

#include<iostream>
#include<cmath>
using namespace std;

/*
求1~n之间的素数个数
*/

// 用n之前的所有数求余，T(n)=O(n^2)
int surplusAll(int n)
{
	// 特殊情况
	if (n <= 0)
	{
		return -1;
	}
	else if (n == 1)
	{
		return 1;
	}

	int total = 1; // 1~n之间的质数个数

	cout << 1 << endl; // 1不判断，直接打出来
	for (int i = 2; i <= n; ++i)
	{
		int j = 2; // 除数

		// 目标数之前是否存在将其整除的数
		while (j != i)
		{
			// 除本身和1之外还有其他因子，非质数，直接跳出，判断下一个
			if (i % j == 0)
				break;
			++j;
		}

		if (j == i )
		{
			++total;
			cout << i << endl;
		}
	}

	cout << endl;
	return total;
}

/* 
* 以1~sqrt(n)为求余判断范围
* 因为如果 m 能被 2~m-1 之间任一整数整除，其两个因子必定有一个小于或等于sqrt(m) ，另一个大于或等于sqrt(m)
* 故只用以sqrt(n)为上限就好
* T(n)=O(n^(3/2))
*/
int surplusSqrt(int n)
{
	// 这里主要是与上述方法对比时间复杂度，就不考虑特殊情况了

	int total = 1; // 1~n之间的质数个数

	cout << 1 << endl; // 1不判断，直接打出来
	for (int i = 2; i <= n; ++i)
	{
		int bound = (int)sqrt(i * 1.0); // 平方根上界
		int j = 2; // 除数

		// 目标数之前是否存在将其整除的数
		for (; j <= bound; ++j)
		{
			if (i % j == 0)
				break;
		}

		// 这里对于2、3这种因平方根小于最小除数（2）未能进入循环的数也是有效的
		if (j > bound)
		{
			++total;
			cout << i << endl; // 输出质数
		}
	}

	cout << endl;
	return total;
}

int main()
{
	cout << surplusAll(20) << endl;
	cout << surplusSqrt(20) << endl;
}