欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

筛法求素数 博客分类: 数学&编程 Scala.net 

程序员文章站 2024-02-16 21:00:46
...
  这属于我用于解Project Euler问题而写的数学工具的一部分。之前见按字典顺序生成所有的排列
/**
   &#Util.scala
   utils for mathematical algorithm,include:
   # get all primes below bound in order
   # generate all permutations in lexicographical order 
   @author Eastsun
*/
package eastsun.math

object Util {
    /**
       Get all primes below bound in order
    */
    def getPrimes(bound:Int):Array[Int] = {
        import scala.math._
        if(bound <= 2) return Array()
        var sq = sqrt(bound-1)
        var half = (bound-1)/2
        var flags = new Array[Boolean](half+1)
        var prime = 3
        while(prime <= sq){
            var idx = prime*prime/2
            while(idx <= half){
                flags(idx) = true
                idx += prime
            }
            do{
                prime += 2
            }while(flags(prime>>>1))
        }
        var count = 1
        var idx = 1
        while(idx <= half){
            if(!flags(idx)) count += 1
            idx += 1
        }
        if((bound-1)%2 == 0 && !flags(half)) count -= 1
        var primes = new Array[Int](count)
        primes(0) = 2
        idx =1
        var idp = 1
        while(idp < count){
            if(!flags(idx)){
                primes(idp) = 2*idx + 1
                idp += 1
            }
            idx += 1
        }
        primes
    }
}
相关标签: Scala .net