1+2+...+n的约数(4) - 他山之石：质数的求解优化

他山之石：质数的求解优化

问题到底是出在哪里了呢？
测试啊测试...
毫无疑问，太多的时间浪费在了质数的求解运算上...
那，就去找质数的优化算法吧...

原版算法代码（计算n以内的质数）：

代码:

#generate prime numbers which are not larger than n
def primes(n)
  primes = Array.new
  i = 2
  while (i <= n)
    #check whether a number is prime
    is_prime = true
    sqrt = Math.sqrt(i).to_i
    primes.each do |prime|
      break if (prime > sqrt)
      is_prime = false and break if (i % prime == 0)
    end 
       
    # prime
    primes << i if is_prime
      
    i += 1
  end
    
  return primes
end

嗯...也许我们可以换个思路...每计算得一个质数m，就更新m~n之间的数：
例如划去2m，3m，4m...这些下次都可以不用计算
等等....那些没被划去的不就是质数吗？

优化后的代码如下：

代码:

def primes(n)
  primes = Array.new(1, 2)
  mark = Array.new(n + 1, true)   
  
  max = Math.sqrt(n).to_i    
  i = 3  
  while (i <= n)    
    # not a prime number, go to next iteration
    i += 2 and next if not mark[i]
    
    # smallest marked number => prime number
    primes << i
    
    # unmark the number who is p*@i
    if (i < max)
      j = i * i
      while (j <= n)
        mark[j] = false #if @mark[@j]
        j += i * 2
      end  
    end
    
    i += 2
  end
  
  return primes  
end

结果是喜人的：在同样的环境下，计算1000000内的质数，第二个算法用了1.7s，而第一个算法用了174s