«

求解1-n之间的素数

1、简陋的算法:
void prime(int n)  
{  
    for (int i = 2; i < n; ++i)  
    {  
        int j;  
        for (j = 2; j <= sqrt(i); ++j)  // 如果i能被2到sqrt(i)之间的所有整数所整除,则其为素数   
        {  
            if (i%j==0) break;  
        }  
        if (j>sqrt(i))   
            cout<<i<<" ";  
    }  
    cout<<endl;  
}  

时间复杂度为O(n*sqrt(n))

2、埃拉托斯特尼筛法:

给出要筛数值的范围n,找出\sqrt{n}以内的素数p{1},p{2},\dots,p_{k}。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。

void primeFilte(int n)  
{  
    bool *filter = new bool[n+1];  
    for (int i=2; i<=n; i++)  
        filter[i] = true;  

    for (int i=2; i<=sqrt(n); i++)  
    {  
        if (filter[i])  
        {  
            int j = i*2;  
            while (j<=n)  
            {  
                if (filter[j])  
                    filter[j] = false;  
                j+=i;  
            }  
        }  
    }  

    for (int i=2; i<=n; i++)  
        if (filter[i]) cout<<i<<" ";  
    cout<<endl;  

    delete []filter;  
}  

时间复杂度为O(n*loglogn),已经是线性时间了

分享