这属于我用于解
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++编程
利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数
### 线性筛法求素数的原理与实现 #### 一、线性筛法的概念及优势 线性筛法是一种高效的算法,能够在O(n)的时间复杂度内找到所有不大于n的素数。相比于传统的遍历取余判断素数的方法,线性筛法在需要频繁判断素数的...
python3的廖雪峰,关于filter,利用埃氏筛法求素数的。
利用C++实现了筛法求素数。代码简洁、明了、易懂。详情见附件。
之前在考研机试的时候看到了这个素数筛法,觉得还挺有趣的。解释下其中的一点,j为什么从i*i开始,按照一般思路应该从i*2开始的,但是仔细分析会发现i*i已经覆盖了i*2这个条件了,因此从i*i开始了。
一、筛法求素数 筛法是求解素数的一种高效算法,最早由古希腊数学家埃拉托斯特尼提出。该算法的基本思想是从2开始,依次将2的倍数标记为合数,然后找到下一个未被标记的数(即3),将其倍数标记,如此循环,直到...
筛选法求素数,在大范围内求素数比其他方法高效很多。
使用数组,运用筛法球素数,效率高,只需该变N的大小变可以求出N以内的素数。
【筛法求素数】是计算数学中一种高效找出一定范围内所有素数的方法,尤其适用于在数组中批量处理。在C语言程序设计中,我们通常使用这种方法来解决如何判断一个整数是否为素数的问题。 首先,素数是大于1且只能被1...
线性筛法求素数的原理与实现 线性筛法是一种高效的算法,它可以在 O(n) 时间内找到所有小于或等于 n 的素数。其核心原理是:每个合数必有一个最大因子(不包括它本身),用这个因子把合数筛掉。通过这种方法,我们...
用厄拉多塞法求素数的C源代码
Jupyter 使用列表实现筛选法求素数 使用列表实现筛选法求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...
python语言对于计算机专业的学生,不管是计算机软件还是物联网,都是很重要的一种编程语言,python未来在人工智能方向上是会有很大的贡献程度...python学习—–使用列表实现筛选法求素数目录一、列表实现筛选法求素数的
源代码 看完写了一个 呵呵 需要的看看
用筛法求素数,将大数分为若干的数组,利用缓存的概念,节省计算时间。
筛选法,也被称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老而高效的寻找所有小于给定数N的素数的方法。以下是筛选法的基本步骤: 1. 创建一个布尔数组,长度为N+1,所有元素初始化为真,表示每个数字...