如何找到R中

Question

連續的合數我想先「N」連續的合數

我搜索命令查找連續的合數，但我得到的結果證明該thorem。我沒有得到任何指令。請幫助我解決這個問題在R.

Answer 1

這確實是一個懶惰的方式提出一個問題，但儘管如此;這應該這樣做：

is_composite<-function(x){ 
      sapply(x,function(y) if(y<3){FALSE}else{any(y%%(2:(y-1))==0)}) 
} 
which(is_composite(1:100)) 

find_N_composites<-function(N){ 
    which(is_composite(1:(2*N+2)))[1:N] 
} 
find_N_composites(10) 

system.time({ 
     x<-find_N_composites(1e+04) 
}) 

這個想法是因此檢查每個數字，如果它有任何除1和除本身之外的除數。我提供的功能在大約2秒內找到前10000個合成數字。如果您希望大數速度更快，優化它會更好。例如，通過僅在簡單數字中查找除數。

Answer 2

這裏是另一種選擇：

n_composite <- function(n) { 

    s <- 4L 
    i <- 1L 
    vec <- numeric(n) 
    while(i <= n) { 

    if(any(s %% 2:(s-1) == 0L)) { 
     vec[i] <- s 
     i <- i + 1L 

    } 

    s <- s + 1L 
    } 

    vec 
} 

它會通過正整數索引複合材料基本控制流循環。

基準

all.equal(find_N_composites(1e4), n_composite(1e4)) 
[1] TRUE 

library(microbenchmark) 
microbenchmark(

    Mak = find_N_composites(1e4), 
    plafort = n_composite(1e4), 
    times=5 

) 

Unit: milliseconds 
    expr  min  lq  mean median  uq 
    Mak 2304.8671 2347.9768 2397.0620 2376.4306 2475.2368 
plafort 508.8132 509.3055 522.1436 509.3608 530.4311 
     max neval cld 
2480.7988  5 b 
    552.8076  5 a 

Answer 3

@Pierre Lafortune的代碼整潔並不算慢，但我想提出另一種方法，它基本上更快。

從另一個角度處理問題，找到R中第一個合成數字n可以翻譯爲「獲得第一個n+k整數並刪除素數」。這很快，因爲生成序列1:(n+k)幾乎沒有時間，並且有非常複雜的算法來查找可用的素數，其中一個是numbers::Primes()。

該序列需要以n+k結尾，因爲在第一個整數中將會有一些（​​）素數需要被替換。請注意，範圍(n+1):(n+k1)也可能包含k2引數，這些引數也需要替換。在...上，在...上，...這將需要一個遞歸結構。

Pierre的答案基本上做了類似的事情：他迭代地檢查一個整數是否是一個合數（非總數），並持續到找到足夠的合成數爲止。然而，這有一個缺點：找到（非）素數的算法是非常天真的（與其他算法相比，找到素數;沒有犯法意圖）。另一方面，該解決方案不涉及上述任何整數範圍內的可能素數的遞歸問題。

遞歸解決方案，我想建議如下：

library(numbers) 

n_composite2 <- function(n, from = 2) { 

    endRange <- from + n - 1 
    numbers <- seq(from = from, to = endRange) 
    primes <- Primes(n1 = from, n2 = endRange) 
    composites <- numbers[!(numbers %in% primes)] 
    nPrimes <- length(primes) 
    if (nPrimes >= 1) return(c(composites, n_composite2(nPrimes, from = endRange + 1))) 

    return(composites) 
} 

這會產生整數（潛在的複合材料）的序列，然後使用numbers::Primes()找到該範圍內的素數，並從其中刪除序列。如果某些數字已被刪除，該函數會再次調用它自己，這次計算組合並從上一步停止的位置開始。

如果有懷疑，這是否實際工作，在這裏對皮埃爾的解決方案的檢查（n_composite()）：

> all(n_composite(1e4) == n_composite2(1e4)) 
[1] TRUE 

比較兩種功能，n_composite2()大約快19倍：

library(microbenchmark) 
microbenchmark(
    "n_composite2" = n_composite2(1e4), 
    "n_composite" = n_composite(1e4), 
    times=5 
) 

Unit: milliseconds 
     expr  min  lq  mean median  uq  max neval 
n_composite2 34.44039 34.51352 35.10659 34.71281 35.21145 36.65476  5 
    n_composite 642.34106 661.15725 666.02819 662.99657 671.52093 692.12512  5 

作爲最後的評論：「皮埃爾的方法和這裏提出的解決方案之間有許多解決方案。人們可以在while循環中使用numbers::Primes()，這與n_composite()中發生的情況非常相似。也可以從「足夠長」的整數序列開始，去除素數，然後取第一個餘數。爲了高效，這種方法需要對給定範圍內的素數數目進行很好的近似處理，這也不是微不足道的（對於低數字）。