poj3006 筛选法求素数模板（数论）

POJ：3006

很显然这是一题有关于素数的题目。

注意数据的范围，爆搜超时无误。

这里要用到筛选法求素数。

筛选法求素数的大概思路是：

如果a这个数是一个质数，则n*a不是质数。

用一个数组实现就是：

memset(prime,true,sizeof(prime));

if (prime[i]) prime[i*j]=false;

部分程序如下：（朴素）

const max=;

bool prime[];

        memset(prime,true,sizeof(prime));

    for(i =  ; i <= ::max ; i ++ )

    {

        for(j =  ; j <= ::max/i ; j ++)

        {

            if(prime[i])

            {

                prime[i * j] = false;

            }

        }

    }

之后将中间进行小小的优化：

我们知道偶数中，除了2，其他的都是合数。

所以就可以将i++ 和 j++改成i+=2,j+=2;

再将除2以外的偶数判为false;以及注意一下特殊的值： 1和0是false;(要记住，c++的数组是从0~max的,所以0要考虑在内）

优化后的程序如下：

const int max = ;

bool prime[]={false};

        memset(prime,true,sizeof(prime));

    for(i =  ; i <=  ; i +=  )

    {

        for(j =  ; j <= ::max / i ; j += )

        {

            if(prime[i])

            {

                prime[i * j] = false;

            }

        }

    }

    for(i =  ; i <= ::max; i +=  )

    {

        prime[i] = false;

    }

    prime[] = prime[] = false;

这样，这题就可以在我们拟好的素数表中找到第n个要求的素数。用一个简单的循环就可以搞定。

附上完整模板：

#include<iostream>

#include<cstring>

using namespace std;

const int max = ;

bool prime[]={false};

int main()

{

    int i,a,d,n,j;

    memset(prime,true,sizeof(prime));

    for(i =  ; i <=  ; i +=  )

    {

        for(j =  ; j <= ::max / i ; j += )

        {

            if(prime[i])

            {

                prime[i * j] = false;

            }

        }

    }

    for(i =  ; i <= ::max; i +=  )

    {

        prime[i] = false;

    }

    prime[] = prime[] = false;

    while(cin >> a >> d >> n,a !=  && d !=  && n != )

    {

        j = ;

        for (i = a; j < n; i += d)

        {

            if (prime[i])

            {

                j++;

            }

        }

        cout << i - d << endl;

    }

    return ;

}

巴特西

poj3006 筛选法求素数模板（数论）

附上完整模板：

最新文章

热门文章