这属于我用于解
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
}
}
分享到:
相关推荐
利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数
数组筛选法求素数c++编程
线性筛法求素数的原理与实现
python3的廖雪峰,关于filter,利用埃氏筛法求素数的。
利用C++实现了筛法求素数。代码简洁、明了、易懂。详情见附件。
之前在考研机试的时候看到了这个素数筛法,觉得还挺有趣的。解释下其中的一点,j为什么从i*i开始,按照一般思路应该从i*2开始的,但是仔细分析会发现i*i已经覆盖了i*2这个条件了,因此从i*i开始了。
筛选法求素数,在大范围内求素数比其他方法高效很多。
用筛法与不要筛法求素数的比较 C++ VC6.0调试成功
使用数组,运用筛法球素数,效率高,只需该变N的大小变可以求出N以内的素数。
讲述O(n)筛法求素数的经典论文 ---------- A Linear Sieve Algorithm for Finding Prime Numbers David Gries Cornell University Jayadev Misra University of Texas at Austin
线性筛法求素数的原理与实现.docx
用厄拉多塞法求素数的C源代码
Jupyter 使用列表实现筛选法求素数 使用列表实现筛选法求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...
第7章 数组——数组的其他应用之筛法求素数C语言程序设计第7章 数组数组的其他应用除了一维、二维数据表、矩阵运算等,还有其他应用吗?问题:如何判断一个整数x是否
每一句都有注释,讲的比较清楚,适合于初学者~~~
源代码 看完写了一个 呵呵 需要的看看
用筛法求素数,将大数分为若干的数组,利用缓存的概念,节省计算时间。
使用筛选法来确定100以内的素数并将其输出 使用时请在dev运行