和果子一起来做题-Project Euler-10-R语言版本

第10题

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

200万以下的质数就和

我们在之前的题目中已经定义过判断质数的函数

findprime <- function(x) {
  if (x %in% c(2,3,5,7)) return(TRUE)
  if (x%%2 == 0 | x==1) return(FALSE)
  xsqrt <- round(sqrt(x))
  xseq <- seq(from=3,to=xsqrt,by=2)
  if (all(x %% xseq !=0)) return(TRUE)
  else return(FALSE)
}

下面就简单了：

a <- 0
for (i in 1:2000000){
  if (findprime(i)== TRUE){
    a = a +i
  }
}

最终a = 142913828922

但是耗时有点久，毕竟数有这么大。

看一下花了多久

> system.time(for (i in 1:2000000){
+              if (findprime(i)== TRUE){
+                a = a +i
+              }
+            })
用户  系统  流逝 
39.99  0.02 40.07

我觉得时间确实说不过去，太长了。一般情况下，我们做的题目如果1秒之内不出答案，基本上就出问题。
我看到有人用[找质数算法之埃拉托色尼筛选法-Sieve of Eratosthenes算法]，这个算法就是先假设每个数都满足条件
然后去掉能被2整除的，再除以能被3整除的，依次算下去，最终留下的就是质数。

我在第三题里面自己写代码实现了一次。但是这次同样的算法，别人的方法更巧妙。

PrimeSieve <- function(n) {
  if (n <= 1) {
    primes <- numeric(0)
  }
  if (n == 2 | n == 3) {
    primes <- 2:n
  }
  else {
    numbers <- 2:n
    sieve <- rep(TRUE, times = n - 1)  # let all flags to be TRUE
    cross.limit <- floor(sqrt(n))
    count <- 1  
    p <- numbers[sieve][count]  # let p be the first sieve number
    while (p <= cross.limit) { #这里就是核心
      sieve[p * (2:floor(n / p)) - 1] <- FALSE
      count <- count + 1
      p <- numbers[sieve][count]
    }  
    primes <- numbers[sieve]
  }
  return(primes)
}
result <- sum(as.numeric(PrimeSieve(2e6)))
cat("The result is:", result, "\n")

大概是2s以内，就算出了答案。

我觉得不满足，高手之间的较量真的是分秒必争，有时候是毫秒必争。在股票世界里有一类稳赚不赔的存在，叫做套利机器人。他不停地计算多个品种之间的差价，同别人争夺购买的权利，他们自己对外的称呼是，我是做固定收益的，我听一个做这这门生意的人说，他每天就是开盘时做个1小时，大概年收入30万，好吧，基本上当你问别人工资时，一般都要打个5-8折，所以他的年收入至少是60万。而当区块链的世界开始时，他们中的聪明人把这个技术用在里交易里面，高手写一个套利程序大概月收入是100万。所以时间就是金钱。
我翻看别人用c语言以及python语言做这道题的结果，大概在0.04s左右，所以钱永远赚不完，但也不是那么好赚。