使用 'which' 了解子集化的行为

Question

我试图定义一个生成所有素数的函数，直到 n。我想出了以下解决方案，我将其与 solution readily available（下面给出以供参考）进行了比较。本质上，这两个代码（如下所示）只有一行差异

sieve <- function(n){
sq.n <- sqrt(n)
vec <- 2:n
primes <- rep(0, times=(sq.n))
i <- 1
while (!(is.na(primes[i] < sq.n)) && (primes[i]) < (sq.n)) {
    primes[i] <- vec[1]
    vec <- vec[which(vec%%primes[i] != 0)] # This keeps all the numbers not divisible by 
    # the prime in question
    i <- i + 1
}
return(c(primes[which(primes!=0)], vec))
}

出于对效率的好奇，google 搜索产生了以下代码 -

getPrimeNumTilln <- function(n) {
a <- c(2:n)
l <- 2
r <- c()
while (l*l < n) {
    r <- c(r,a[1])
    a <- a[-(which(a %% l ==0))] # This removes all the numbers which are 
    # divisible by the prime in question
    l <- a[1]
}
c(r,a)
}

两种解决方案都可以。（如果n是素数的平方，网上的答案会给出错误的答案，但很容易纠正）

这些是微基准测试结果 -

microbenchmark(sieve(100),getPrimeNumTilln(100),times=100)
Unit: microseconds
                  expr     min      lq      mean  median      uq     max neval
            sieve(100) 142.107 153.106 165.85155 162.785 165.425 466.795   100
 getPrimeNumTilln(100)  41.797  47.076  51.09312  49.276  51.036 126.269   100

我想了解这两个函数在运行时的公平差异

Answer 1

第一个函数的循环为 n = 100 进行了 10 次迭代，第二个函数进行了 4 次迭代。

sieve <- function(n){
  sq.n <- sqrt(n)
  vec <- 2:n
  primes <- rep(0, times=(sq.n))
  i <- 1
  while (!(is.na(primes[i] < sq.n)) && (primes[i]) < (sq.n)) {
    count <<- count + 1
    primes[i] <- vec[1]
    vec <- vec[which(vec%%primes[i] != 0)] # This keeps all the numbers not divisible by 
    # the prime in question
    i <- i + 1
  }
  return(c(primes[which(primes!=0)], vec))
}

count <- 0
sieve(100)
#[1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
count
#[1] 10

getPrimeNumTilln <- function(n) {
  a <- c(2:n)
  l <- 2
  r <- c()
  while (l*l < n) {
    count <<- count + 1
    r <- c(r,a[1])
    a <- a[-(which(a %% l ==0))] # This removes all the numbers which are 
    # divisible by the prime in question
    l <- a[1]
  }
  c(r,a)
}

count <- 0
getPrimeNumTilln(100)
# [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
count
#[1] 4

使用 'which' 了解子集化的行为

Understanding the behaviour of subsetting using 'which'

r

sieve-of-eratosthenes