质数筛法

埃式筛
原理：如果 x是质数，那么x的倍数 2x,3x… nx一定不是质数
输入一个数n，就可以知道1-n中有多少个质数：

        int n;
	int ret = 0;
 	cin>>n;
 	int* prime = new int[n];
 	memset(prime, 1, sizeof(prime));
	prime[1] = 0;
 	for (int i = 2; i <= n; ++i)
{
 		if (prime[i])
 		{
 			ret++;
 			for (int j = i; j * i <= n; ++j)
				prime[i * j] = 0;
		}
	}
	cout << ret;
       delete[]prime;

如果需要把质数打印出来，需要改动一点点，如下：

去掉:ret++；int ret=0;

改成：cout<<i<<" ";