編輯：厄蘭的eratophenes最高的主要因素的篩選

我已編輯程序，以便它的工作（小數字），但我不明白如何實現一個累加器建議。原因是因爲P在整個過程中都發生了變化，所以我不知道應該用哪個粒度來分解母表。這個eratophenes篩只對產生較小的素數有效，所以也許我應該選擇一個不同的算法來使用。任何人都可以推薦一個體面的算法來計算最高的素因子600851475143？請不要給我代碼我寧願維基百科的那種性質的文章。編輯：厄蘭的eratophenes最高的主要因素的篩選

-module(sieve). 
    -export([find/2,mark/2,primes/1]). 

    primes(N) -> [2|lists:reverse(primes(lists:seq(2,N),2,[]))]. 

    primes(_,bound_reached,[_|T]) -> T; 
    primes(L,P,Primes) -> NewList = mark(L,P), 
     NewP = find(NewList,P), 
     primes(NewList,NewP,[NewP|Primes]). 

    find([],_) -> bound_reached; 
    find([H|_],P) when H > P -> H; 
    find([_|T],P) -> find(T,P). 


    mark(L,P) -> lists:reverse(mark(L,P,2,[])). 

    mark([],_,_,NewList) -> NewList; 
    mark([_|T],P,Counter,NewList) when Counter rem P =:= 0 -> mark(T,P,Counter+1,[P|NewList]); 
    mark([H|T],P,Counter,NewList) -> mark(T,P,Counter+1,[H|NewList]).

我發現寫作這很困難，我知道有一個關於它的一些事情，是不是很優雅，比如我有2硬編碼爲一個素數的方法。因此，我將不勝感激任何C和建議如何攻擊這些問題。我看着其他的實現，我絕對不知道作者如何用這種方式思考，但我想要掌握的東西。

新：我已經計算出，直到找到最新的素數，我才能忘記列表，但是我不知道我該如何產生一個結束界限（微妙的幽默）。我認爲可能有些東西我可以像列表一樣使用：seq（P，something），Counter可以處理它，因爲我使用的是模數，而不是每次都將其重置爲0。我只做過AS級數學，所以我不知道這是什麼。

New2.0：我甚至不能這樣做我可以嗎？因爲我將不得不從整個列表中刪除2的倍數。我認爲這種算法不會工作，除非我緩存數據到硬盤，所以我回來尋找一個更好的算法。

New2.5：我現在正在考慮編寫一個算法，只使用一個計數器並保持一個素數列表，這些素數不能與以前生成的素數均勻分配，這是一個很好的方法嗎？

New3.0：這是我寫的新算法，我認爲它應該工作，但我得到以下錯誤「sieve2.erl：7：調用本地/導入函數is_prime/2是非法守衛」我想這只是erlang的一個方面，我不明白。不過，我不知道如何找到要閱讀的材料。 [林故意沒有使用高階函數等，因爲我只在learnyousomeerlang.org遞歸讀取高達位]

-module(sieve2). 
    -export([primes/1]). 

    primes(N) -> primes(2,N,[2]). 

    primes(Counter,Max,Primes) when Counter =:= Max -> Primes; 
    primes(Counter,Max,Primes) when is_prime(Counter,Primes) -> primes(Counter+1,Max,[Counter|Primes]); 
    primes(Counter,Max,Primes) -> primes(Counter+1,Max,Primes). 

    is_prime(X, []) -> true; 
    is_prime(X,[H|T]) when X rem H =:= 0 -> false; 
    is_prime(X,[H|T]) -> prime(X,T).

編輯3.5：第二個算法不會崩潰，但速度太慢，即時通訊思想我應該做的重新實現第一次，但這次忘記了數字，直到最近發現的素數，是否有人知道我可以用作最終界限？在尋找其他的解決方案後，人們似乎有時只是設置一個arbitary限制，即2元（這是我真的不想做其他使用「懶」的實現是什麼，我認爲我做的

來源

2013-02-26 George Payne

這裏有人試圖解決你完全相同的問題，但不是在Erlang。評論和答案可能有幫助。 http://stackoverflow.com/questions/439814/prime-factor-of-300-000-000-000 – kjw0188 2013-03-02 09:03:08

此。：

lists:seq(2,N div 2)

分配列表，並且作爲efficiency guide說，列表需要的每個元素存儲至少兩個單詞。（A字是4或8個字節，這取決於是否有32位或64位二郎山虛擬機。）所以，如果N是600851475143，這將需要的存儲TB級48，如果我算正常。（不像哈斯克爾，二郎沒有做懶惰的評價。）

所以你需要實現這個使用蓄能器，類似於您Counter在mark功能做了什麼。對於遞歸函數的停止條件，您不會檢查列表是否爲空，而是累加器達到最大值。

來源

2013-02-26 14:57:35 legoscia

順便說一句，你不需要測試所有數字高達N/2。測試達到sqrt（N）就足夠了。

Here I wrote a version that takes 20 seconds to find the answer on my machine.它使用一種懶惰的素數列表並摺疊通過它們。這很有趣，因爲我很久以前就用Haskell解決了一些項目問題，並且在Erlang上使用相同的方法有點奇怪。

來源

2013-02-26 18:45:16

如果你除以你發現的因素將會快得多。 – starblue 2013-02-27 21:53:18

劃分什麼？我有一個素數列表，我把它們中的每一個都寫到sqrt（N），並檢查一個素數是否是N的一個因子。 – 2013-02-28 08:10:11

N，所以剩下的數字變得小得多。 – starblue 2013-02-28 17:15:21

在您UPDATE3：

primes(Counter,Max,Primes) when Counter =:= Max -> Primes; 
primes(Counter,Max,Primes) when is_prime(Counter,Primes) -> primes(Counter+1,Max,[Counter|Primes]); 
primes(Counter,Max,Primes) -> primes(Counter+1,Max,Primes).

你不能使用自己定義的函數作爲保護條款在哈斯克爾。你必須重寫它在case語句中使用它：

primes(Counter,Max,Primes) when Counter =:= Max -> 
    Primes; 
primes(Counter,Max,Primes) -> 
    case is_prime(Counter,Primes) of 
     true -> 
      primes(Counter+1,Max,[Counter|Primes]); 
     _ -> 
      primes(Counter+1,Max,Primes) 
    end.

來源

2013-02-28 08:14:29

編輯：厄蘭的eratophenes最高的主要因素的篩選

回答

相關問題