AcWing 868. 筛质数

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1000005;
int primes[N],cnt;
bool st[N];
void get_primes(int n){//埃氏筛统计素数
  for(int i=2;i<=n;i++){
    if(!st[i]){
      primes[cnt++]=i;
      for(int j=i*2;j<=n;j+=i) st[j]=true;
    }   
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  get_primes(n);
  printf("%d\n",cnt);
  //for(int i=0;i<cnt;i++) cout<<primes[i]<<" ";
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1000005;
int primes[N],cnt;
bool st[N];
void get_primes(int n){//线性筛  
  for(int i=2;i<=n;i++){
    if(!st[i]) primes[cnt++]=i;
    for(int j=0;primes[j]<=n/i;j++){
      st[primes[j]*i]=true;
      if(i%primes[j]==0)break;//primes[j]一定是i的最小质因子
    }     
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  get_primes(n);
  printf("%d\n",cnt);
  //for(int i=0;i<cnt;i++) cout<<primes[i]<<" ";
    return 0;
}
/*
n只会被最小质因子筛掉
1. i%primes[j]==0 
   primes[j]一定是i的最小质因子  primes[j]一定是primes[j]*i的最小质因子
2. i%primes[j]!=0
   primes[j]一定小于i的所有质因子  primes[j]一定是primes[j]*i的最小质因子
对于一个合数x，假设primes[j]是x的最小质因子，当i枚举到x/primes[j]的时候这个合数会被筛掉
*/