求小于n的所有素数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int vis[N];
int n;
void primes(int n){
	memset(vis,0,sizeof(vis));
	vis[1] = 1;
	for(int i=2;i<=n;i++){
		if(vis[i]==0){
			cout<<i<<endl;
			for(int j=i;j<=n/i;j++){
				vis[i*j]=1;
			}
		}
	}
}
int main(){
	cin>>n;
	primes(n);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int v[N],p[N],n,m;
// v数组下标为所有自然数，值为该自然数的最小素因子
// p数组下标为第几个素数，值为素数的值
void primes(int n){//线性筛函数
	memset(v,0,sizeof(v));//把v数组所有值初始化为0,默认所有数暂时都是素数
	for(int i=2;i<=n;i++){// 循环n-1次，把2~n的所有事拿出来筛选
		if(v[i]==0){// v[i]==0代表i是素数，否则是则是合数
			v[i] = i;//素数的最小素因子是自己
			cout<<"素数"<<i<<endl;
			cout<<"标记"<<i<<":"<<v[i]<<endl;
			p[++m]=i;
		}
		cout<<"开始标记"<<i<<"的倍数"<<endl;
		for(int j=1;j<=m;j++){//循环m次，把已经记录的素数都遍历出来和i相乘，作为一个新数的素因子
			if(p[j]>v[i]||p[i]>n/i){
				break;
			}
			v[i*p[j]]=p[j];
			cout<<"标记"<<i*p[j]<<":"<<p[j]<<endl;
		}
	}
	for(int i=1;i<=m;i++){
		cout<<"!"<<p[i]<<endl;
	}
}
int main(){
	cin>>n;//求0~n，有多少个素数
	primes(n);//调用线性筛函数
	return 0;
}

前100个素数