素數發生器中的遞歸

我正在做一個素數生成器，並且爲了使它更有效率，我試圖只測試數字，而不是我已經找到的素數，而不是測試數量的所有數字< sqrt 。我試圖讓我成爲我的素數列表，但我不知道如何讓它在我的第二個循環內重現。我認爲這只是針對a <- 2測試，不a <- c(a,i)素數發生器中的遞歸

x <- 3:1000 
a <- 2 
for (i in x) 
{for (j in a) 
    {if (i %% j == 0) 
    {next} 
    else {a <- unique(c(a,i))}}} 
a

來源

2010-10-04 user446667

看到這個答案http://stackoverflow.com/questions/3789968/generate-a-list-of-primes-in-r-up-to-a-certain-編號/ 3791284＃3791284 – John 2010-10-05 04:08:50

您還希望在'x'中切出偶數，並定期增加'a'的大小，而不是每次增加以提高速度。 – James 2010-10-05 09:20:18

使用簡單素數函數的非遞歸模型的速度與您在R中所做的一樣快，如下所示。不是循環每個單獨的值並測試它的優勢，而是去除大塊中所有質數的倍數。這將每個隨後的剩餘值隔離爲一個主要部分。所以，它取出2倍，然後3倍，然後4不見了，所以5倍值。這是做在河的最有效的方式

primest <- function(n){ 
    p <- 2:n 
    i <- 1 
    while (p[i] <= sqrt(n)) { 
     p <- p[p %% p[i] != 0 | p==p[i]] 
     i <- i+1 
    } 
    p 
}

（您可能希望看到用篩子我的函數的時序更快的方法，也this棧的問題。什麼是上面會運行50，也許500X快比你工作的版本。）

來源

2010-10-05 13:56:26 John

運行非常好，謝謝 – user446667 2010-10-07 17:43:59

的解決方案可能是削減了第二循環，而不是比較你提出的素數對整個矢量代替，如：

x <- 3:1000 
a <- 2 
for (i in x) { 
    if (!any(i %% a == 0)) { 
    a <- c(a,i) 
    } 
}

這似乎對我有用。

來源

2010-10-04 20:50:29 Wine

素數發生器中的遞歸

回答

相關問題