algorithm - 生成不超过一定数量的素数列表

Question

我正在尝试生成一个小于 10 亿的素数列表。我正在尝试这个，但这种结构非常糟糕。有什么建议吗？

a <- 1:1000000000
d <- 0
b <- for (i in a) {for (j in 1:i) {if (i %% j !=0) {d <- c(d,i)}}}

Answer 1

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
}

顺便说一句，spuRs 包有许多主要的查找功能，包括 E 的筛选。还没有检查过它们的速度如何。

虽然我正在写一个很长的答案......如果一个值是素数，你将如何检查 R。

isPrime <- function(x){
    div <- 2:ceiling(sqrt(x))
    !any(x %% div == 0)
}