当前位置:编程学习 > C/C++ >>

筛素数解法

常用的筛素数的算有两种:
1). Eratosthenes筛法:把[1,N]素数p的倍数筛出去,剩余的就是素数。
[cpp]  
int prime[N], np;  
bool vis[N];  
void get_prime()  
{  
    np = 0;  
    memset(vis, 0, sizeof(vis));  
    for(int i = 2; i < N; ++i)  
    {  
        if (!vis[i])  
        {  
            prime[np++] = i;  
            for(int j = i+i; j < N; j +=i) vis[j] = 1;  
        }  
    }  
}  
 
算法复杂度O(N*log log N)
2). 线线筛法:Eratosthenes筛易做图有很多重复的筛选,此算法是对Eratosthenes筛法的改进.
线性筛素数的基本思想是:每个合数只被筛一次,将被其最大因数筛掉。
 
假设我们依据flag数组从小到大判断每个数是否是素数,如果当前该数还未被筛掉,那么就是素数,因为在比它小的数中没有发现因数,将素数加入素数表中。对每一个数i(不论素数或合数),用它筛掉flag数组中以它为最大因数的数。因为每个数只去筛以它为最大因数的数,所以每个合数只会被一个数筛,就是它的最大因数,以此达到线性的复杂度。www.zzzyk.com
 
假设当前的数是i。以i为最大因数的数是哪些呢?这些数必然是i乘上一个比它小的素数(如果该数是i乘上一个比它大的素数,显然i不会是该数的最大因数;如果是i乘上一个合数x = p1*p2*...*pk (pi为素数),显然通过将x的一些素因数与i相乘会得到比i大的因数)。
 
假设i可以表示为素数乘积:i = p1*p2*...*pn,x是一个比i小的素数(x显然已经被筛出来了,在我们的素数表中),其中i最小的素因数是p1。i只有与当前素数表中p<=p1的素数相乘,得到的数y才以i为最大因数。反证:如果i乘上pm得到y = i*pm,且pm>p1,那么y有因数y/p1 > i = y/pm。
 
所以对每一个数i,乘上素数表中不大于i的最小素因数p1的素数,将得到的数从flag数组中筛去,我们就可以在线性的时间复杂度下得到一个素数表。
[cpp] 
int prime[N], np;  
bool vis[N];  
void get_prime2()  
{  
    np = 0;  
    memset(vis, 0, sizeof(vis));  
    for (int i = 2; i < N; ++i)  
    {  
        if (!vis[i]) prime[np++]=i;  
        for (int j = 0,t ; j < np && (t = prime[j]*i) < N; ++j)  
        {  
            vis[t] = 1;  
            if(i % prime[j] == 0) break;  
        }  
    }  
}  
在该算法中,每个合数都只被最小的素数筛去,算法复杂度O(N)
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,