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

本文介绍了生成不超过一定数量的素数列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I'm trying to generate a list of primes below 1 billion. I'm trying this, but this kind of structure is pretty shitty. Any suggestions?

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

推荐答案

这是 Sieve ofR中的Eratosthenes算法.

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)