AcWing 868. java同学
原题链接
简单
作者:
季之秋
,
2021-01-24 09:45:58
,
所有人可见
,
阅读 295
import java.util.*;
public class Main{
static int n,N=1000010;
static boolean st[]=new boolean[N];
static int primes[]=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int cnt=0;
/*朴素做法
for(int i=2;i<=n;i++){
if(!st[i]){ //是不是质数
cnt++; //st[n]=false就代表2到n-1里都没有n的因子,
}
for(int j=i*2;j<=n;j+=i)
st[j]=true; //用筛去每个数的倍数
}
*/
/*埃式做法
for(int i=2;i<=n;i++){
if(!st[i]){//把每个质数的倍数去除,(质数的倍数就是合数)
cnt++;//st[n]=false就代表2到n-1里都没有n的因子,
for(int j=i*2;j<=n;j+=i) //用质数去筛去合数
st[j]=true;
}
}
*/
//线性做法
for(int i=2;i<=n;i++){//i=a*b*c,用最小质因数更筛掉每一个合数
if(!st[i]) primes[cnt++]=i;//质数从小到大排序
for(int j=0;primes[j]*i<=n;j++){//j是质数
if(i%primes[j]!=0){ st[i*primes[j]]=true; }//pj<i最小质因数、pj就是 i*primes[j] 最小质因数
else { st[i*primes[j]]=true;break; }
//pj就是i最小质因数、pj也就是 i*primes[j] 最小质因数
} //所以,p[j+1]肯定不是p[j+1]*i的最小质因数,因为p[j]是i的最小质因数,
} //而p[j]又比p[j+1]小,所以防止重复(相等于每个质数j会乘j到n/j的数i,)
//举个例子,pj=2,i=4;那么2肯定是8的最小质因数,p[j+1]=3,p[j+1]*i=12,我们不需要拿3去筛掉12,
//因为当i=6的时候,pj*i=2*6=12会把12筛掉,以此类推,后面就没必要执行了,break掉
//,同理,pj=3,i=5,那么3不是5的最小质因数,而且3是质数没有因数。所以3肯定是15的最小质因数;15就可以筛掉,
// 然后p[j+1]=5,5是5的最小质因数(两个原因,第一个p[j]恒<=i,p[j+1]=0所以没必要执行下去了)
//,第二个,如果有 p[j+1]=7,7*5=35,最小质因数是5不是p[j+1] ,这个35可以等p[j]=5,i=7的时候筛掉,
System.out.println(cnt);
}
}