poj2909 欧拉素数筛选

刚刚学了一种新的素数筛选法，效率比原先的要高一些，据说当n趋近于无穷大时这个的时间复杂度趋近O(n)。本人水平有限，无法证明。

这是道水题，贴代码出来重点是欧拉筛选法。我把原来普通的筛选法贴出来。

//2013-11-07-22.30

//poj 2909

#include <stdio.h>

#include <string.h>

const int maxn = (1<<15)+5;

bool vis[maxn];

int pr[3416];

int cnt = 1;

void getpr()

{

    for (int i = 2; i < maxn; i++)

    {

        if (vis[i] == 0)

            pr[cnt++] = i;

        for (int j = 1; j < cnt; j++)

        {

            if (i*pr[j] > maxn)

                break;

            vis[i*pr[j]] = 1;

            if (i%pr[j] == 0)

                break;

        }

    }

}

//void getpr()

//{

//    for (int i = 2; i < maxn; i++)

//    {

//        if (vis[i])

//            continue;

//        else

//            pr[cnt++] = i;

//        for (int j = i<<1; j < maxn; j += i)

//            vis[j] = true;

//    }

//}

int main()

{

    int n;

    getpr();

    while (scanf("%d", &n) && n)

    {

        int m = n>>1;

        int ans = 0;

        for (int i = 1; i < cnt; i++)

        {

            if (pr[i] > m)

                break;

            if (vis[n-pr[i]] == 0)

                ans++;

        }

        printf("%d\n", ans);

    }

    return 0;

}

我把vis改成int型，然后对代码稍微改了一下，增加了计算总共访问过多少次vis数组的功能，欧拉筛法共访问29258次，而普通筛分访问了80298次，明显效率更低一些，改动代码如下，有兴趣可以自己试试。

//2013-11-07-22.30

//poj 2909

#include <stdio.h>

#include <string.h>

const int maxn = (1<<15)+5;

int vis[maxn];

int pr[3416];

int cnt = 1;

//void getpr()  //欧拉筛法

//{

//    for (int i = 2; i < maxn; i++)

//    {

//        if (vis[i] == 0)

//            pr[cnt++] = i;

//        for (int j = 1; j < cnt; j++)

//        {

//            if (i*pr[j] > maxn)

//                break;

//            vis[i*pr[j]]++;

//            if (i%pr[j] == 0)

//                break;

//        }

//    }

//}

void getpr() //普通筛法

{

    for (int i = 2; i < maxn; i++)

    {

        if (vis[i])

            continue;

        else

            pr[cnt++] = i;

        for (int j = i<<1; j < maxn; j += i)

            vis[j]++;

    }

}

int main()

{

    int n;

    getpr();

    int sum = 0;

    for (int i = 1; i < maxn; i++)

        sum += vis[i];

    printf("sum = %d\n", sum);

    while (scanf("%d", &n) && n)

    {

        int m = n>>1;

        int ans = 0;

        for (int i = 1; i < cnt; i++)

        {

            if (pr[i] > m)

                break;

            if (vis[n-pr[i]] == 0)

                ans++;

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

poj2909 欧拉素数筛选

最新文章

热门文章