随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

求2-nMax的素数

今天本来打算学习散列表的，看了一下，发现你面很多地方用到素数，所以就写了一个求素数的程序，很有大一的感觉。呵呵。奉上源代码：

#include <stdio.h>
#include <stdlib.h>

int g_nPrime[100000];

//求nMax范围类最多不超过nLen个素数，把结果保存在nPrime中。
//返回素数的个数
int GetPrimeNumbers(int nPrime[], int nLen, int nMax)
{
    //如果空间为0，或nMax小于2则返回没有求道素数。
    if (nMax < 2 || nLen <= 0)
    {
        return 0;
    }

    
    int nNumber = 1;    //初始个数为1个(即2这个素数)
    nPrime[0] = 2;    
    int nPos = 0;        //是除比较时候的最大下标。这样可以节省一小小时间

    for (int i = 3; i < nMax && nNumber < nLen; ++i)
    {
        int j;

        //遍历要除的素数，如果都不能整除，则i为素数。
        for ( j = 0; j <= nPos; ++j)
        {
            if (i % nPrime[j] == 0)
            {
                break;
            }
        }

        if (j > nPos )    //都不能整除，i是素数
        {
            nPrime[nNumber] = i;    //保存到nprime中，并个数加1
            ++nNumber;
        }
        else if (j == nPos && i == nPrime[nPos] * nPrime[nPos])
        {
            //如果该数位最大下标对应值的平方，最大下标加1
            ++nPos;
        }
    }

    return nNumber;
}
int main()
{
    //测试一把，不过比较花，改为1000就不错。呵呵。
    int nNumber = GetPrimeNumbers(g_nPrime, 100000, 100000000);
    for (int i = 0; i < nNumber; ++i)
    {
        printf("%d ", g_nPrime[i]);
    }
    system("pause");
    return 0;
}

//为什么这么增加一个最大求余地下标，主要是为了提高点效率。如果一个数字在一个素数的
//平方范围内，则只需要对比他小的素数求余就可以了。这样可以提高
//一点点时间。我看了一下120万中有10万个素数，如果加上最大求余下标，就只需到1000
//这样的话可以省略掉1000-1百万之间的所有素数求余，也就是省略了大概9万个数据。很客观的。

posted on 2009-05-04 19:42 shongbee2 阅读(540) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理