Eratosthenes筛选求质数

    除自身之外，无法被其他整数整除的数称为质数，质数的求法很简单，但如何快速的求出质数一直是程序员与数学家努力的课题，这里介绍一个著名的Eratosthenes求质数的方法。
解法
首先知道这个问题可以使用循环来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少循环的检查次数?如何求出小于N的所有质数？

首先假设要判断的数是Ｎ，则事实上只要检查到Ｎ的平方根就可以了，道理很简单，假设Ａ＊Ｂ＝Ｎ，如果Ａ大于Ｎ的平方根，则事实上在小于Ａ之前的检查就可以先检查到Ｂ这个数可以整除Ｎ。不过在程序中使用平方根会有精确度的问题，所以可以使用ｉ＊ｉ<=Ｎ进行检查，且执行更快。

再来假设有一个筛子存放１～Ｎ，例如
2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　19　20　21 ........ N
先将２的倍数筛去：   
2　3　5　7　9　11　13　15　17　19　21 ........ N
再將3的倍數篩去：
2　3　5　7　11　13　17　19　........ N
再來將5的倍数筛去，再來將7的质数筛去，再來將11的倍數筛去........，如此进行到最后留下的數就都是質數，這就是Eratosthenes筛选方法（Eratosthenes Sieve Method）。

检查的次數还可以再減少，事實上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍数，使得程序中的if的检查动作可以減少。

def findPrimes(max)
  prime=[1]*max
  for i in 2..Math.sqrt(max).to_int
    if prime[i]==1
      for j in 2*i..max
        if j%i==0
          prime[j]=0
        end
      end
    end
  end
  t=[]
  prime.each_index{|i|t<<i if prime[i]==1 and i>1}
   p t
end
primes=findPrimes(1000)