基础定义

质数:是指在大于1的自然数中，除了$1$和它本身以外不再有其他因数的自然数。(也就是说在$1$到$n$中只有两个因数)

因数(约数):如果$a$除以$b$余数为$0$,那么$b$是$a$的因数

基于理解的写法

int c=0;
for(int i=1;i<=n;i++) //枚举1到n中的所有整数 
{
    if(n%i==0) //说明i是n的因数 
    {
        cnt++;//因数个数增加 
    }
}
if(c==2) //说明n是因数 
{
  
}

基于定义的写法

bool st=true;//刚开始是满足的
if(n<2) //不满足定义 
{
    st=false;
} 
for(int i=2;i<=n-1;i++) //枚举2到n-1之间的所有数 
{
    if(n%i==0) //说明2到n-1存在因子(n不是质数) 
    {
        st=false;
    }
}
if(st) //状态没有更新过,说明n是质数
{
  
} 

优化写法

bool st=true;//刚开始是满足的
if(n<2) //不满足定义 
{
    st=false;
} 
for(int i=2;i<=n/i;i++) //枚举2到sqrt(n)之间的所有数 
{
    if(n%i==0) //说明2到sqrt(n)存在因子(n不是质数) 
    {
        st=false;
    }
}
if(st) //状态没有更新过,说明n是质数
{
  
} 

题目描述

输入数字$n$，输出$1 \sim n$之间所有的质数。

数据范围

1.$1 \leq n \leq 10^4$

算法分析

枚举1到n之间的所有数,然后用朴素判定法即可.

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int cnt=0;//素数个数
	for(int i=2;i<=n;i++)
	{
		bool st=true;
		for(int j=2;j<i;j++)
		{
			if(i%j==0) //说明i不是质数 
			{
				st=false;
			}
		}
		if(st) cnt++;
	} 
	cout<<cnt;
	return 0;
}

数据范围

2.$1 \leq n \leq 10^6$

算法分析

枚举1到n之间的所有数,然后用优化素数判定法即可.

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int cnt=0;//素数个数
	for(int i=2;i<=n;i++)
	{
		bool st=true;
		for(int j=2;j<=i/j;j++)
		{
			if(i%j==0) //说明i不是质数 
			{
				st=false;
			}
		}
		if(st) cnt++;
	} 
	cout<<cnt;
	return 0;
}

数据范围

3.$1 \leq n \leq 10^7$

算法分析

埃拉托斯特尼筛法（Sieve of Eratosthenes）,使用当前素数去标记所有的数.

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
bool st[N];
int main()
{
	int n;
	cin>>n;
	int cnt=0;//质数的个数 
	for(int i=2;i<=n;i++)
	{
		if(st[i]==0) //说明i是一个质数
		{
			cnt++;
			for(int j=i*i;j<=n;j+=i)
			{
				st[j]=1; //表示j不是质数	
			}	
		} 
	}
	cout<<cnt;
	return 0;
}

数据范围

3.$1 \leq n \leq 10^8$

算法分析

欧拉筛(线性筛),在筛质数的时候,保证每个数只会被分解质因数以后最小的质数筛掉.

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
bool st[N];
vector<int> p;
int main()
{
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		if(st[i]==0) p.push_back(i);
		for(int j=0;p[j]<=n/i;j++)
		{
			st[i*p[j]]=1;
			if(i%p[j]==0)
			{
				break;
			}
		}
	}
	cout<<p.size();
	return 0;
}