C++(clang++ 11.0.1) 解法, 执行用时: 24ms, 内存消耗: 948K, 提交时间: 2023-07-07 09:01:03

#include <bits/stdc++.h>
using namespace std;
int a[100010];

int prime(int n)
{
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0)
			return 0;
	}
	return 1;
}

int main()
{
	int n;
	cin>>n;
	for(int i=2;i<=n+2;i++){
		if(prime(i))
			a[i]=1;
		else
			a[i]=2;
	}
	if(n<3)
		cout<<1<<endl;
	else
		cout<<2<<endl;
	for(int i=2;i<n+2;i++){
		cout<<a[i]<<" ";
	}
	return 0;
 } 

C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 888K, 提交时间: 2019-08-21 22:08:42

#include<bits/stdc++.h>
using namespace std;
int ans[100005];
int main(){
	int n;
	scanf("%d",&n);
	int mx=1;
	memset(ans,0,sizeof(ans));
	for(int i=2;i<=n+1;i++){
		if(ans[i]==0){
			ans[i]=1;
			int t=ans[i];
			for(int j=i*2;j<=n+1;j+=i)
				ans[j]=2,mx=max(mx,ans[j]);
		}
	}
	printf("%d\n",mx);
	for(int i=2;i<=n+1;i++)
		printf("%d ",ans[i]);
	return 0;
}