yolo_mm 用筛法求之N内的素数

解题思路:

    常规筛，把倍数筛去

注意事项:

    i*i  而不是从2倍筛起，比如i=5,如果是两倍则在i=2的时候就已经筛去了

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N=1000;

int vis[N];

int tot[N];

bool is_prime(int x){

 for(int i=2;i*i<x;i++){

  if(x%i==0) return false;

  return true;

 }

} 

int main(){

 int N,k=0;

 cin>>N;

 memset(vis,0,sizeof(vis));

 for(int i=2;i<=N;i++){

  if(vis[i]==0){

   vis[i]=1;

   if(is_prime(i)) tot[k++]=i;

  }

  for(int j=i*i;j<=N;j+=i) vis[j]=1;

 }

 for(int i=0;i<k;i++){

  cout<<tot[i]<<endl;

 }

}