算法-素数

素数

素数，也称作质数，是数学领域和计算机领域经常涉及到的概念。我之前也有遇到过此类题，如：鉴别一个数是否是素数? 或者，打印出2~100之间的素数？(1不是素数)

概念

如果一个数，只能被1和它本身整除，则此数为素数。素数的个数是无穷的，见 欧几里得的证明。

编码实现

搜索一下，能看到许多素数的代码实现，我找到一篇能符合我以前心境的文章（并非好的实现方式）： JavaScript判断数字是否为质数的方法汇总 我也有时候像这篇文章的作者，考虑的太过多了，比如：

• 通过for循环从2~n 来判断;

• 2~n效率比较低，改为2~(n+1)/2;

  很简单嘛,一下子就实现了.但是,好像可以优化一下.我们 好像不必一直追到这个数字去求余数,我们好像只需要循环到这个 数的一半,就可以计算出来这个数字是不是质数了. (源自文中)

• 不计算数字尾数为双数或者5的数字(其实5也是素数，这有个bug);

• 进行 如果不是数字或者整数的处理；

• 去除能被3整除的数字不计算；

• 去除能被5整除的数字不计算；

最终文章的作者发现了用Math.sqrt(num)，求平方根的方式，发现那些多余的计算全部都是负优化..

---

下面是一些代码实现：

JavaScript代码段:

let i = 2;

while (i <= 100) {
	let j = 2;
	while (j <= Math.sqrt(i)) {
		if ((i % j) === 0) { // 能整除 
			break;
		}
		j++;
	}
	if (j > Math.sqrt(i)) {
		console.log(`${i}是素数`);
	}
	i++;
}

Python代码段:

# -*- coding: UTF-8 -*-
i = 2
while(i < 100):
   j = 2
   while(j <= (i/j)):
      if not(i%j): break
      j = j + 1
   if (j > i/j) : print i, "素数"
   i = i + 1
 
print "Good bye!"

为何程序计算素数只需计算 2~√m(假设需计算的数字为m)?

解释:

m不必被2~m-1之间的每一个整数去除，只需被2~√m之间的每一个整数去除就可以了。
如果m不能被2~√m间任一整数整除，m必定是素数。 例如判别17是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。 例如16能被2,4,8整除，16=2*8,2小于4, 8大于4;
16=4*4, 4=√16，因此只需判定在2~4之间有无因子即可）xxxxxxxxxx // 0 1 2 3 4// 0 1 1 2 3   :   0 1 1 => 1 1 2 => 1 2 3 => 2 3 5const fib2 = (n) => {  if (n === 0 || n === 1) {    return n; }  let a = 0,    b = 1,    sum = a + b;  // n:2 应为1 : 1 1 2  // n:3应为2: 1 2 3  for (let i = 2; i <= n; i++) {    a = b;    b = sum;    sum = (a + b) % 1000000007; }  return b;};js