筛法求素数 博客分类: 数学&编程 Scala.net
程序员文章站
2024-02-16 15:32:58
...
这属于我用于解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 } }