暴力

依据素数定义，将每个数循环次\(\sqrt{n}\),一共有n个数，时间复杂度为O(n\(\sqrt{n}\)).

#include 
#include 

int prime(int n) {
	if (n == 1)
		return 0;
	int cnt = 0;
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			return 0;
			cnt = 1;
		}
	}
	return 1;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		if (prime(i))
			printf("%d\n", i);
	}
	return 0;
}

埃式算法

利用素数的倍数必定数合数的特性，将合数给筛查掉,时间复杂度是O(nloglogn)(不会推，寄了)

#include 
#include 
int isprime[10010];

void check(int n) {
	memset(isprime, 1, sizeof(isprime));
	isprime[0] = isprime[1] = 0;
	for (int i = 2; i <= n; i++) {
		if (isprime)
			for (int j = i * 2; j <= n; j += i)
				isprime[j] = 0;
	}
}

int main() {
	int n;
	scanf("%d", &n);
	check(n);
	for (int i = 1; i <= n; i++) {
		if (isprime[i])
			printf("%d\n", i);
	}
	return 0;
}

欧拉筛法

埃式筛法的缺点是对同一个合数重复筛查，而欧拉筛法对此进行了优化，一个合数只筛一次,因此时间复杂度为O(n)
欧拉筛法把从2， 3， 5....到小于 i 的最大素数分别和 i 相乘得到的数标记成合数。并且过程中一旦发现 i % （p[j]） == 0，则跳出循环，这样做保证了每个合数只被他的最小素因子筛到一次.

#include 
int prime[10010];
int isprime[10010], cnt;

void check(int n) {
	for (int i = 2; i <= n; i++) {
		if (!isprime[i])
			prime[cnt++] = i;
		for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
			isprime[i * prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	check(n);
	for (int i = 0; prime[i] != 0; i++)
		printf("%d\n", prime[i]);
	return 0;
}