素数筛法(埃氏筛法、线性筛法)

素数筛法:用于筛选出素数 核心思想:用一个数筛选其余的数

普通筛法: 时间复杂度为O(nlogn)

#include <iostream>
#define N 100
bool vis[N] = { false };// 0到N-1的元素都没有被标记
int primes[N]; // 存放素数
int tot; 


//普通筛法
int main() {
	vis[0] = vis[1] = true; // 0和1不是素数

	for (int i = 2; i < N; i++) {
		if (!vis[i]) {
			primes[++tot] = i; // 找到一个素数，存放到primes中
		}
		for (int j = 2 * i; j < N; j += i) {
			vis[j] = true; // 将i的倍数都标记为已被筛掉
		}
	}

	for (int i = 1; i < tot; i++) {
		std::cout << primes[i] << " ";
	}
	std::cout << std::endl;
	return 0;
}

继续优化的话可以 只用质数去筛 ，这也就是埃氏筛法: 时间复杂度为:O(nloglogn)

int main() {
	vis[0] = vis[1] = true; // 0和1不是素数
	for (int i = 2; i < N; i++) {
		if (!vis[i]) {
			primes[++tot] = i; // 找到一个素数，存放到primes中
			for (int j = i * i; j < N; j += i) {
				vis[j] = true; // 将i的倍数都标记为已被筛掉
			}
		}
	}

	for (int i = 1; i < tot; i++) {
		std::cout << primes[i] << " ";
	}
	std::cout << std::endl;
	return 0;
}

继续优化 线性筛 : 每个数都被其最小的质因数筛掉 时间复杂度为O(n)

int main() {
	vis[0] = vis[1] = true;
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) {
			primes[++tot] = i;
		}
		for (int j = 1; i * primes[j] < N; j++) {
			vis[i * primes[j]] = true;
			if (i % primes[j] == 0) {
				break;
			}
		}
	}

	for (int i = 1; i < tot; i++) {
		std::cout << primes[i]<< " ";
	}
	std::cout << std::endl;

	return 0;
}