526互联

数学相关算法

发布时间 2024-01-06 18:23:31作者: 毛竹先生

埃氏筛

#include<bits/stdc++.h>
using namespace std;

int a[50000005] = {};
int n = 0;

int main()
{
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++) a[i] = 1;
	for(int i=2; i<=n; i++)
	{
		if(a[i] == 0) continue;
		for(int j=i; j<=n/i; j++)
		{
			a[i*j] = 0;
		}
	}
	for(int i=2; i<=n; i++)
	{
		if(a[i]) printf("%d\n", i);
	}
	
	return 0;
}

线性筛

#include<bits/stdc++.h>
using namespace std;

int a[50000005] = {};
int prim[50000005] = {}, cnt = 0;
int n = 0;

int main()
{
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++) a[i] = 1;
	for(int i=2; i<=n; i++)
	{
		if(a[i]) prim[++cnt] = i;
		for(int j=1; j<=cnt; j++)
		{
			if(i*prim[j] > n) break;
			a[i*prim[j]] = 0;
			if(i%prim[j] == 0) break;
		}
	}
	for(int i=1; i<=cnt; i++) 
		printf("%d\n", prim[i]);
	
	return 0;
}