0

我在 RStudio 版本 0.97.336 中使用 R 版本 2.15.3 (2013-03-01) - Xubuntu 12.10 3.8.8-030808-generic 上的“安全毯”。

我编写了一个算法，它为 Project Euler 的第五个问题提供了一个通用的解决方案：

“2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。

可以被 1 到 20 的所有数字整除的最小正数是多少？”（http://projecteuler.net/problem=5）？

程序不断发现 min=116396280，而答案是 232792560(2*116396280)。单击我们的测试向量会显示 test[16]=7274767.5，但是，手动输入test[16]会返回 7274768。此外，当手动输入时，应该identical(test,floor(test))返回。FALSE为什么当 R 经历这些循环时它忽略了这个事实7274767.5!=floor(7274767.5)？

pe5<-function(n){
  p<-c()
  for(x in 1:n){
    while(x!=1){
      y<-2
      z<-0
      while(x!=z){
        z<-x/y
        if(z==floor(z)){
          x<-z
          p<-append(p,y)
        }else{
          y<-y+1
        }
      }
    }
  }
  min<-0
  test<-rep(0,n)
  x<-2520
  while(min==0){
    for(i in unique(p)){
      test[i]<-x/i
    }
    if(identical(test,floor(test))==TRUE){
      min<-x
    }else{
      x<-x+2520      
    }
  }
  print(min)
}
pe5(20)
4

2 回答 2

1

为什么当 R 经历这些循环时它忽略了这个事实7274767.5!=floor(7274767.5)？

它没有。你永远不会让它在这些循环中检查。

让我们看看你的代码做了什么：

p<-c()
for(x in 1:n){
  while(x!=1){
    y<-2
    z<-0
    while(x!=z){
      z<-x/y
      if(z==floor(z)){
        x<-z
        p<-append(p,y)
      }else{
        y<-y+1
      }
    }
  }
}

对于从 1 到n您的每个数字，您将其素因数附加到p（最初为空），每个数字与它在素因数分解中出现的频率一样多。

所以在那之后，p包含所有的素数<= n，其中一些是多次的（我想，我不知道 R，所以我不能 100% 确定它append()会做我认为的事情），素数大于n/2一次。

for(i in unique(p)){
  test[i]<-x/i
}
if(identical(test,floor(test))==TRUE){
  min<-x
}else{
  x<-x+2520      
}

对于 中列出的每个素数p，您检查当前候选是否x是它的倍数。如果它不是其中一个素数的倍数，则增加x2520。

由于 2520 已经可以被所有正整数整除<= 10，因此您实际上是在检查 2520 的倍数是否也可以被 11、13、17 和 19 整除。

现在，对于素数π > 10，k*2520是π当且仅当k是 的倍数时的倍数π，所以你计算的是

2520*11*13*17*19 = 2³ * 3² * 5 * 7 * 11 * 13 * 17 * 19

你从来没有在你的算法中真正考虑过素数，所以你总是得到2520 * product of the primes > 10 in the range. 对于上限 20，唯一能被< 10比 2520 更高的素数（或素数的平方> 10）整除的数字是 16，所以这是你唯一的“失败案例”。

如果你用更大的界限来测试它会更明显，因为n = 25你会得到一个太小的结果2*5[2 from 16, and one 5 from 25 = 5²]，因为n = 27结果太小了一个因素2*3*5[也是来自27 = 3³]的3。

您需要找到每个素数不超过 的最高幂n，结果是这些素数幂的乘积。

于 2013-04-21T15:48:12.750 回答
0

正如所承诺的，虽然有点延迟，但这是一个可行的解决方案。我追求的是程序的效率，而不是编码，但我敢打赌，有一种更短的方法可以编写更高效的脚本（请随时在这方面提出建议或发布您自己的解决方案）。我还编码，如果我错了，请纠正我，我的第一个人工智能进入这个程序。

n<-500
if(!exists("primeslist",mode="numeric")){
    primeslist<-(2)
  }
  q<-matrix(rep(NA,n*floor(log(n,2))),n,floor(log(n,2)))
  for(i in 2:n){
    j<-1
    x<-as.numeric(i)
    while(x!=1){
      k<-1
      y<-primeslist[k]
      z<-1
      while(x!=z){
        z<-x/y
        if(z==floor(z)){
          x<-z
          q[i,j]<-y
          j<-j+1
          if(y>tail(primeslist, 1)){
            primeslist<-append(primeslist, y)
          }
        }else{
          if(tail(primeslist, 1)>y){
            k<-k+1
            y<-primeslist[k]
          }else{
            y<-y+1
          } 
        }
      }
    }
  }
  t<-unique(as.vector(q))
  t<-t[!is.na(t)]
  padicmat<-matrix(rep(0, n*3),n,3)
  padicmat[,1]<-1:n
  for(i in t){
    padicrow<-rep(NA,n)
    for(j in 1:n){
      padicrow[j]<-length(which(q[j,]==as.numeric(i)))
    }
    padicmat[i,2]<-max(padicrow)
  }
padicmat[,3]<-padicmat[,1]^padicmat[,2]
result<-prod(padicmat[,3])
result
于 2013-05-01T09:18:54.093 回答