乔治·唐塔斯发布的那个筛子是一个很好的起点。这是一个更快的版本,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
}
顺便说一句,spuRs 包有许多素数查找功能,包括 E 筛。还没有检查过它们的速度如何。
虽然我正在写一个很长的答案...以下是您如何检查 R 是否有一个值是素数。
isPrime <- function(x){
div <- 2:ceiling(sqrt(x))
!any(x %% div == 0)
}