如何提高筛选法求大范围素数的效率

学习一下这种求素数的算法
服务器君一共花费了537.860 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

素数的定义:只能被1和它自己整除的自然数称为素数,特别规定1不属于素数。

根据素数的定义,很明显,如果一个数是素数<==>它的因子只包含1和它本身。因此可以根据判别某个数的因子的方法来判断其是否是素数。

int isprime(int n)
{
    int i;
    for(i=2;i<=(int)sqrt((double)n);i++)
    {
        if(n%i==0)    //如果n存在其它因子,则必定不是素数
         {
            return 0;
        }
    }
    return 1;
}

但是如果要求求出1000000以内的所有素数,上面的方法效率就很低,因此通常采用筛选法去求素数。筛选法:对于一个数n,如果是素数,那么2*n,3*n,4*n,必定不是素数。

bool isprime[1000001];
int prime[80000];
int num=0;
void getPrime()     //用筛选法求算素数
{
    int i,j;
    for(i=0;i<1000001;i++)
    {
        isprime[i]=true;
    }
    for(i=2;i<=1000;i++)        //如果isprime[i]==true,即i是素数,那么i,2*i,3*i必定不是素数
     {
        for(j=i+i;j<=1000000;j+=i)
        {
            if(isprime[i]==true)
                isprime[j]=false;
        }
    }
    for(i=2;i<1000001;i++)
    {
        if(isprime[i]==true)
        {
            prime[num++]=i;
        }
    }
}

筛选法求素数有一个很通用的算法,就是在遍例该集合时,比方检验一个数N是否素数,用N除以2-N的开方,只要有一个能整除,就说明N不是素数。另外这道题要求用数组来计算。

所谓"筛选法"指的是"埃拉托色尼(Eratosthenes)筛法"。他是古希腊的著名数学家。他采取的方法是,在一张纸上写上1到100全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。

具体做法如下:

  1. 先将1挖掉(因为1不是素数)。
  2. 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。
  3. 用3去除它后面的各数,把3的倍数挖掉。
  4. 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1~50的素数,要一直进行到除数为47为止(事实上,可以简化,如果需要找1~n范围内素数表,只需进行到除数为n^2(根号n),取其整数即可。例如对1~50,只需进行到将50^2作为除数即可。)

如上算法可表示为:

  1. 挖去1;
  2. 用刚才被挖去的数的下一个数p去除p后面各数,把p的倍数挖掉;
  3. 检查p是否小于n^2的整数部分(如果n=1000, 则检查p<31?),如果是,则返回(2)继续执行,否则就结束;
  4. 纸上剩下的数就是素数。
#include <stdio.h>
#include <math.h>
int main(void)
{
    int i;
    int j;
    int a[101];                // 为直观表示,各元素与下标对应,0号元素不用
    for (i = 1; i <= 100; i++) // 数组各元素赋值
        a[i] = i;
    for (i = 2; i < sqrt(100); i++)     // 外循环使i作为除数
        for (j = i + 1; j <= 100; j++)  // 内循环检测除数i之后的数是否为i的倍数
        {
            if (a[i] != 0 && a[j] != 0) // 排除0值元素
                if (a[j] % a[i] == 0)
                    a[j] = 0;           // i后数若为i的倍数,刚将其置0(挖去)
        }
    int n = 0;    // 对输出素数计数, 以控制换行显示
    for (i = 2; i <= 100; i++)    // 输出素数
    {
        if (a[i] != 0)
        {
            printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数)
            n++;
        }
        if (n == 10)
        {
            printf("\n");         // 每行10个输出
            n = 0;
        }
    }
    printf("\n");
    return 0;
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/1350,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1350

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《深入理解MySQL核心技术》 Sasba Pacbev (作者), 李芳 (译者), 于红芸 (译者), 邵健 (译者)

《深入理解MySQL核心技术》:从公共可用性的意义上讲,MySQL源代码是开放源代码,但如果对其不了解,则实质上,它对于您来说是封闭的。MysQL开发团队的前成员Sasha Pachev通过《深入理解MySQL核心技术》给出了MySQL 5的全面指南,揭示了这一强大数据库的内部运作。您将直奔MySQL核心技术,了解各种数据结构和各种方便的功能的运作情况,了解如何添加新的存储引擎和配置选项等。 《深入理解MySQL核心技术》从结构概况讲起,在这一部分解释了MysQL的不同组件是如何协同工作的。接着将学习设置有效的可编译代码副本的步骤,然后使用基本架构添加自己的配置变量和存储引擎。

更多计算机宝库...