生成一个素数列表，直到某个数字为止
我正在尝试生成一个低于10亿的素数列表。我正在尝试这种方式，但是这种结构非常糟糕。有什么建议吗？
a <- 1:1000000000
d <- 0
b <- for (i in a) {for (j in 1:i) {if (i %% j !=0) {d <- c(d,i)}}}回答 11
Stack Overflow用户
发布于 2010-09-25 03:26:30
这是Sieve of Eratosthenes算法在R中的一个实现。
sieve <- function(n)
{
n <- as.integer(n)
if(n > 1e6) stop("n too large")
primes <- rep(TRUE, n)
primes[1] <- FALSE
last.prime <- 2L
for(i in last.prime:floor(sqrt(n)))
{
primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE
last.prime <- last.prime + min(which(primes[(last.prime+1):n]))
}
which(primes)
}
sieve(1000000)Stack Overflow用户
发布于 2010-09-25 05:52:30
George Dontas发布的筛子是一个很好的起点。这是一个更快的版本，1e6质数的运行时间为0.095秒，而原始版本的运行时间为30秒。
sieve <- function(n)
{
n <- as.integer(n)
if(n > 1e8) stop("n too large")
primes <- rep(TRUE, n)
primes[1] <- FALSE
last.prime <- 2L
fsqr <- floor(sqrt(n))
while (last.prime <= fsqr)
{
primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE
sel <- which(primes[(last.prime+1):(fsqr+1)])
if(any(sel)){
last.prime <- last.prime + min(sel)
}else last.prime <- fsqr+1
}
which(primes)
}下面是一些用R编写的尽可能快的替代算法，它们比筛子慢，但比提问者的原始帖子快得多。
下面是一个使用mod的递归函数，但它是矢量化的。它几乎在瞬间返回1e5，在2秒内返回1e6。
primes <- function(n){
primesR <- function(p, i = 1){
f <- p %% p[i] == 0 & p != p[i]
if (any(f)){
p <- primesR(p[!f], i+1)
}
p
}
primesR(2:n)
}下一个不是递归的，而且速度更快。在我的机器上，下面的代码在1.5秒内完成了1e6的素数。
primest <- function(n){
p <- 2:n
i <- 1
while (p[i] <= sqrt(n)) {
p <- p[p %% p[i] != 0 | p==p[i]]
i <- i+1
}
p
}顺便说一句，马刺的包有一些主要的查找功能，包括一个E的筛子。我还没有检查他们的速度是什么样子。
当我写一个很长的答案的时候...如果有一个值是质数，下面是如何检入R的。
isPrime <- function(x){
div <- 2:ceiling(sqrt(x))
!any(x %% div == 0)
}Stack Overflow用户
发布于 2010-09-25 02:47:20
据我所知，生成所有素数的最好方法(不用进入疯狂的数学)是使用Sieve of Eratosthenes。
它的实现非常简单，允许您不使用除法或模数来计算素数。唯一的缺点是它是内存密集型的，但可以进行各种优化来提高内存(例如，忽略所有偶数)。
https://stackoverflow.com/questions/3789968
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号