Question

使用函数调用从键盘输入一个整数n，并输出1-n所有素数！

Answer 1

一个直观的算法是检验2~n中每个数是不是素数，但检验一个数m是不是素数需要验证2~√m是不是2的因子，时间复杂度是O(√m)，因此这种算法的时间复杂度是O(√2+√3+...+√n)=O(n√n)。

另一个算法是从2~n中依次删除2,3,……的倍数（如果这个数已经被删除，就不用考虑了。比如4在删除2的倍数时被删除了，因此删除3的倍数后不考虑4，直接删除5的倍数），那么剩下的就是素数。删除m的倍数的时间复杂度是O(n/m)，因此这种算法的时间复杂度是O(n(1+1/2+...+1/n))=O(nlog n)，当n非常大时会比上面的算法快。

以下是这种算法的C++程序实现：

#include <deque>
#include <iostream>
using namespace std;
void output_prime(unsigned n)
{
	deque<bool> is_prime(n + 1, true);
	//删除所有大于2的偶数
	for (unsigned i = 4; i <= n; i += 2) is_prime[i] = false;
	for (unsigned i = 3; i <= n / 2; i += 2) {
		if (is_prime[i]) {//只有i之前没被删除才删除i的倍数
			for (unsigned j = i * 2; j <= n; j += i) 
				is_prime[j] = false;
		}
	}
	for (unsigned i = 2; i <= n; ++i) 
		if (is_prime[i]) cout << i << endl;
}
int main() {
	unsigned n;
	cin >> n;
	output_prime(n);
	return 0;
}

Answer 2

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX 50000

int num[MAX];

void init()
{
int i,j;

memset(num,0,sizeof(num));
for(i=2; i<MAX; i++)
for(j=2; j*i<MAX; j++)
if( num[i] == 0 )
num[j*i] = 1;
}

int Analy(int n)
{int i;
for (i=2; i<=n; i++)
if(!num[i]) printf("%d\n", i);
}
int main()
{
init();
int n;
scanf("%d",&n);
Analy(n);
return 0;
}