优化素数查找器和cpu速度检查器在R

Question

我有以下代码在10秒内找到素数:

prime_nums = function (){
    ptm <- proc.time()
    p_nums = c(2)
    counter = 2
    while (TRUE){
        isPRIME = FALSE
        counter = counter +1
        for(n in p_nums) {
            if(n > sqrt(counter)){ isPRIME=TRUE; break; }
            if(counter %% n == 0){ isPRIME = FALSE; break;}
        }
        if(isPRIME) { p_nums[length(p_nums)+1]=counter ; cat("",counter,";")}
        if((proc.time()[3]-ptm[3]) > 10) break; 
    }
}

然而，这是用许多循环编写的，这些循环在r中通常不受欢迎。我如何优化这段代码，使其尽可能快?

---

编辑:我发现下面的代码是最快的:

prime_nums_fastest = function (){
    ptm <- proc.time()
    p_nums = c(2L,3L,5L,7L)
    counter = 7L
    while (TRUE){
        isPRIME = FALSE
        counter = counter +2L       
        loc = 4*sqrt(counter)/log(counter,2)   
        isPRIME = !any(0 == (counter %% p_nums[1:loc]))
        if(isPRIME) { p_nums[length(p_nums)+1]=counter }
        if((proc.time()[3]-ptm[3]) > 10) break;
    }
    print(p_nums)
}

为了简化，保留

初始小素数。使用2 *√…甚至是3*根号下。For loc参数导致包含非素数。与使用1:sqrt(counter)相比，需要检查的质数明显减少。

Answer 1

删除cat命令。这是昂贵的。有了它，我得到384239。而返回质数向量的结果是471617，这是一个显著的改进。

将n > sqrt(counter)更改为n*n > counter使我得到477163，这是一个小小的改进。

将p_nums和counter更改为integer类型使我获得514859，另一个小改进。这是通过修改定义和调整的行来实现的:

p_nums = c(2L)
counter = 2L
# ... and inside the loop:
  counter = counter +1L

请注意，您可以将确定一个值为素数的循环向量化，代码如下:

isPRIME = !any(0 == (counter %% p_nums[1:sqrt(counter)]))

使用它而不是for让我得到451249，一个显著的回归(不使用cat并使用整数算术)。这是因为R没有延迟列表求值，所以对每个值取模数，然后对0进行测试。在这种情况下，这是for的优势。