素数(质数)筛选法

给定一个正整数N，求出【2、N】中的所有素数。

两种实现方法

//素数(质数)筛选法 O(NlogN)
function getPrime(n){
    const arr=[]
    const ans=[];
    let d=0;
    for(let i=2;i<=n;i++)arr[i]=true
    for(let i=2;i<=n;i++){
        if(n/i<i)break;
        for(let j=i*i;j<=n;j+=i){
            arr[j]=false
        }
    }
    for(let i=2;i<=n;i++)if(arr[i])ans[d++]=i;
    console.log(ans)
}
getPrime(10)

　　

//素数(质数)筛选法O(N)
function getPrime(n){
    const arr=[]
    const ans=[];
    let tot=0;
    for(let i=2;i<=n;i++){
        if(!arr[i]){
            ans[tot++]=i;
        }

        for(let j=0;j<tot&&i*ans[j]<=n;j++){
            arr[i*ans[j]]=true;
            if(i%ans[j]==0)break;
        }
    }
    console.log(ans)
}
getPrime(10)