11.素数判断及打印素数表-优化版

1. 素数判断

素数定义：除了1和本身以外，不能被任何其他整数整除的一类数；

<mark>如果这个数X，isprime（x）返回1则是素数 返回0则非素数</mark>

int isprime(int x)
{
	if(x<=1) return 0;
	for(int i=2;i<sqrt(x);i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
} 
int main()
{
	cout<<isprime(x);//x为判断的数
	return 0;
}

2.素数表的获取

<mark>①暴力枚举</mark>
根据时间复杂度 n<100000 都是没问题的
时间复杂度O（n根号n）

int isprime(int x)
{
	if(x<=1) return 0;
	for(int i=2;i<sqrt(x);i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
} 
int main()
{
	cout<<isprime(x);//x为判断的数
	return 0;
}


int main()
{
	int n;// 根据时间复杂度 n<100000 都是没问题的
	cin>>n;  // 求2-n之间的所有素数
	for(int i=2;i<=n;i++)
	{
		if(isprime(i)) cout<<i<<endl;
	} 
	return 0;
}

<mark>②埃尔筛法</mark>
根据时间复杂度 n<10000000 都是没问题的
时间复杂度O（nloglogn）

#include <bits/stdc++.h>
using namespace std;
const int maxn=100;//这里是求1-100间的素数表
int a[maxn+1],cn=0;//cn计数素数的多少 同时为存放素数的数组a当成下标使用
bool p[maxn+1]={false}; //p重元素flase表示为素数 true表示非素数
void findprime()
{
	for(int i=2;i<=maxn;i++)
	{
		if(p[i]==false) a[cn++]=i;  //flase是素数处存入a数组
		for(int j=i+i;j<=maxn;j=j+i)
		{
			p[j]=true; //将a中的素数的所有倍数定义为非素数
		} 
	}
}
int main()
{
	findprime();
	for(int i=0;i<cn;i++)  cout<<a[i]<<endl;  //输出
	return 0;
}

<mark>③欧拉筛法</mark>
点我直达