生成一个质数列表
我正试图产生一个低于10亿的素数列表。 我正在尝试，但这种结构是相当低劣的。 有什么build议么？
a <- 1:1000000000 d <- 0 b <- for (i in a) {for (j in 1:i) {if (i %% j !=0) {d <- c(d,i)}}} 这是R 的Eratosthenesalgorithm的实现。
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)
乔治·杜塔斯（George Dontas）发布的筛选是一个很好的起点。 这是一个更快的版本，运行时间为0.095s的1e6素数，而原始版本为30s。
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中尽可能快地编码的一些替代algorithm。它们比筛子慢，但是比提问者原始post快得多。
这是一个recursion函数，使用mod但是是vector化的。 它几乎瞬间返回1e5，在2s以下返回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) }
下一个不是recursion的，而且更快。 下面的代码会在我的机器上大约1.5s内达到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包有一些主要的发现function，包括E筛。还没有检查看看他们的速度是什么。
而当我正在写一个很长的答案…这是如何检查R如果一个值是总理。
isPrime <- function(x){ div <- 2:ceiling(sqrt(x)) !any(x %% div == 0) }
最好的方式，我知道产生所有的素数（没有进入疯狂的math）是使用Eratosthenes筛 。
这是相当直接的实施，并允许你计算素数，而不使用除法或模数。 唯一的缺点是内存密集，但是可以进行各种优化来提高内存（例如忽略所有的偶数）。
我build议primegen ， 丹伯恩斯坦执行的阿特金伯恩斯坦筛。 速度非常快，可以很好地适应其他问题。 你需要传递数据到程序来使用它，但我想有办法做到这一点？
这种方法应该更快更简单。
allPrime <- function(n) { primes <- rep(TRUE, n) primes[1] <- FALSE for (i in 1:sqrt(n)) { if (primes[i]) primes[seq(i^2, n, i)] <- FALSE } which(primes) }
我的电脑上0.12秒， n = 1e6
我在函数AllPrimesUpTo的包primefactr中实现了这个。
你也可以在schoolmath包中作弊和使用primes()函数：D
上面发布的isPrime（）函数可以使用sieve（）。 只需要检查是否有任何素数<ceiling（sqrt（x））除以x就没有余数。 还需要处理1和2。
isPrime <- function(x) { div <- sieve(ceiling(sqrt(x))) (x > 1) & ((x == 2) | !any(x %% div == 0)) }
for (i in 2:1000) { a = (2:(i-1)) b = as.matrix(i%%a) c = colSums(b != 0) if (c == i-2) { print(i) } }
将（a）之前的每个数字（i）与通过检查数字（i-1）而生成的素数（n）
感谢您的build议：
prime = function(a,n){ n=c(2) i=3 while(i <=a){ for(j in n[n<=sqrt(i)]){ r=0 if (i%%j == 0){ r=1} if(r==1){break} } if(r!=1){n = c(n,i)} i=i+2 } print(n) }
