即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

筛法求素数 – Ruby

编程语言 jtahstu 44℃ 0评论
本文目录
[隐藏]

1.筛法求素数

用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。 –来自百度百科

代码中介绍了两种写法,查阅资料时有看到其他的写法,这里主要关注思想,效率还有待优化,这两种写法效率都不怎样,是有更好的写法的,那就自行Google吧。

# author: jtusta
# contact: root@jtahstu.com
# site: http://www.jtahstu.com
# software: RubyMine
# time: 2017/6/7 15:41
class Prime
  @@array = Array.new 105,1

  def initialize(n=100)
    @n = n
  end

  # 筛法求素数,乘法
  def do
    for i in 2..@n
      for j in 2..@n/i
        @@array[i*j]=0
      end
    end
  end

  # 筛法求素数,加法
  def do_2
    for i in 2..@n-1
      @@array[i] = i%2==0?0:1
    end
    @@array[2]=1  # 特别的2是素数
    i = 3
    while i<=Math.sqrt(@n)
      if @@array[i]==1
        j = i+i
        while j<@n
          @@array[j]=0
          j+=i
        end
      end
      i+=2
    end
  end

  # 输出数组
  def put
    for i in 2..@n
      if @@array[i]==1
        print i,' '
      end
    end
    puts
  end
end

prime = Prime.new
prime.do
prime.put

prime2 = Prime.new
prime2.do_2
prime2.put

各种变形中的一种,自己理解吧

#define MAX_N 1000  
int a[MAX_N+1];  
int p[MAX_N+1];  
int nCount=0;  

void Init(int n) //线性筛法,不过在小范围上(约n<1e7)不比上一个方法快  
{  
    for (int i=2;i<=n;i++)  
    {  
        if (a[i]==0)  
        {  
            p[++nCount]=i;  
        }  
        for (int j=1,k; (j<=nCount) && (k=i*p[j])<=n; j++) //筛选循环  
        {  
            a[k] = 1 ;  
            if (i%p[j] == 0) break;  
        }  
    }  
}  

#include   
int main(void)  
{  
    Init(MAX_N);  
    for(int n=1; p[n]>1; ++n)  
    {  
        printf("%5d", p[n]);  
    }  
    return 0;  
}

1.1.1.素数相关知识

最大公约数只有1和它本身的数叫做质数(素数)——这个应该知道吧?-_-b

至今为止,没有任何人发现素数的分布规律,也没有人能用一个公式计算出所有的素数。关于素数的很多的有趣的性质或者科学家的努力。

  1. 高斯猜测,n以内的素数个数大约与n/ln(n)相当,或者说,当n很大时,两者数量级相同。这就是著名的素数定理。  
  2. 十七世纪费马猜测,2的2^n次方+1,n=0,1,2…时是素数,这样的数叫费马素数,可惜当n=5时,2^32+1就不是素数,至今也没有找到第六个费马素数。
  3. 18世纪发现的最大素数是2^31-1,19世纪发现的最大素数是2^127-1,20世纪末人类已知的最大素数是2^859433-1,用十进制表示,这是一个258715位的数字。
  4. 孪生素数猜想:差为2的素数有无穷多对。目前知道的最大的孪生素数是1159142985×2^2304-1和1159142985×2^2304+1。
  5. 歌德巴赫猜想:大于2的所有偶数均是两个素数的和,大于5的所有奇数均是三个素数之和。其中第二个猜想是第一个的自然推论,因此歌德巴赫猜想又被称为1+1问题。我国数学家陈景润证明了1+2,即所有大于2的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。

转载请注明:CodingBlog » 筛法求素数 – Ruby

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情