AcWing 868. 筛质数 java
原题链接
简单
作者:
吴鑫
,
2021-02-13 16:50:48
,
所有人可见
,
阅读 279
import java.util.*;
public class Main{
final static int N=1000010;
static int n,cut;
static int[] prime=new int[N];
static boolean[] st=new boolean[N];
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
get_prime();
System.out.print(cut);
}
static void get_prime(){
for(int i=2;i<=n;i++){
if(!st[i]) prime[cut++]=i;
for(int j=0;prime[j]<=n/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
}