线性筛法（最小质因数）

//线性筛法-找质数以及每个数的最小质因数
#include<iostream>

using namespace std;

const int N=1e5+10;

int n,p[N],minp[N];  //p[N]存质数 minp[N]存每个数的最小质因子
int cnt;
bool st[N]; 
void get_p(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i])
		{
		//	st[i]=true;
			minp[i]=i;  //质数i的最小质因子是本身
			p[cnt++]=i;  //存质数 
		}
		for(int j=0;p[j]*i<=n;j++)
		{
			st[p[j]*i]=true; //标记每个合数
			minp[p[j]*i]=p[j]; //此循环中每个合数的最小质因子都是p[j]
			if(i%p[j]==0)
			break; 
		}
	 } 
}

int main(void)
{
	cin>>n;
	get_p(n);
	for(int i=0;i<cnt;i++)
	cout<<p[i]<<' ';
	cout<<endl;
	for(int i=1;i<=n;i++)
	cout<<minp[i]<<' ';
	return 0;
 }