The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
+-%echo+-%prime_listecho(Message,Sender)->Sender ! Message.+-%prime_iteratorprime_list()-> case whereis(primeList) of undefined-> Pid=spawn(euler,prime_list,[initialize]), register(primeList, Pid), Pid; Exists-> Exists end. prime_list(initialize)-> put(primes,array:from_list([2,3,5,7,11,13,17,19])), put(total,8), prime_list(idle); prime_list(idle)-> Size=get(total), receive {get,FromZero,Reply} when FromZero < Size -> Reply ! {prime,FromZero,array:get(FromZero,get(primes))}; {get,FromZero,Reply} -> echo({get,FromZero,Reply},self()), prime_list(gen); {all_below,What,Reply} -> case array:get(Size-1,get(primes)) < What of true-> prime_list(gen), echo({all_below,What,Reply},self()); false-> Reply ! {primes_below,What,prime_list(below,What,0,[])} end; {is_prime,What,Reply}-> Skirt=math:sqrt(What), Largest=array:get(Size-1,get(primes)), case Largest < What of true-> case Largest < Skirt of true-> prime_list(gen), echo({is_prime,What,Reply},self()); false-> Reply ! {is_prime,What,prime_list(check_factors,0,What,Skirt)} end; false-> Reply ! {is_prime,What,prime_list(binary_search,What,0,Size-1)} end end, prime_list(idle); prime_list(gen)-> Size=get(total), Start=array:get(Size-1,get(primes))+2, End=Start*10+1, Sqrt=math:sqrt(End), AsList=array:to_list(get(primes)), [2|Odds]=AsList, RelevantOdds=lists:takewhile(fun(N)->N =< Sqrt end,Odds), Newbs=prime_list(gen,Size,Start,End,RelevantOdds,ordsets:from_list(lists:seq(Start,End,2))), put(primes,array:from_list(lists:append(AsList,ordsets:to_list(Newbs)))), put(total,get(total)+ordsets:size(Newbs)). prime_list(check_factors,NextIndex,N,Sqrt)-> NextPrime=array:get(NextIndex,get(primes)), case NextPrime > Sqrt of true->true; false-> case N rem NextPrime ==0 of true->false; false-> prime_list(check_factors,NextIndex+1,N,Sqrt) end end; prime_list(binary_search,What,Low,High) when High-Low < 2 -> H=array:get(High,get(primes)), L=array:get(Low,get(primes)), if H == What; L == What -> true; true->false end; prime_list(binary_search,What,Low,High)-> Mid=Low+((High-Low) div 2), Got=array:get(Mid,get(primes)), if What > Got->prime_list(binary_search,What,Mid+1,High); What < Got->prime_list(binary_search,What,Low,Mid-1); true->true end; prime_list(below,What,Index,SoFar)-> Next=array:get(Index,get(primes)), if Next >= What-> lists:reverse(SoFar); true-> prime_list(below,What,Index+1,[Next|SoFar]) end. prime_list(gen,_,_,_,[],Survivors)->Survivors; prime_list(gen,Total,Lowest,Highest,[MyPrime|RestPrimes],Survivors)-> prime_list(gen,Total,Lowest,Highest,RestPrimes, ordsets:subtract(Survivors, ordsets:from_list( lists:seq(Lowest-(Lowest rem MyPrime),Highest,MyPrime)))).p10()-> Iter=prime_iterator(self()), p10(0,Iter). p10(Sum,Iter)-> Iter ! next, Next=receive {prime,X}->X end, if Next < 2000000 ->p10(Sum+Next,Iter); true->io:format("~w~n",[Sum]) end.prime_iterator(Pid)->spawn(euler,prime_iterator,[idle,0,2,Pid,prime_list()]). prime_iterator(idle,Index,Next,Parent,List)-> receive next-> Parent ! {prime, Next}, List ! {get, Index+1,self()}, prime_iterator(wait,Index+1,nothing,Parent,List) end; prime_iterator(wait,Index,_,Parent,List)-> receive {prime,Index,Next}-> prime_iterator(idle,Index,Next,Parent,List) end.
+-#PrimeListdef p10 p=PrimeList.new sum=0 sum+=p.last while p.getNext<2000000 puts sum endclass PrimeList @@primes=[2,3,5,7,11,13,17,19] def initialize @next=-1 end def last return 0 if @next==-1 PrimeList.get(@next) end def getNext PrimeList.get(@next+=1) end def [](i) PrimeList.get(i) end def PrimeList.isPrime?(n) if(@@primes[-1] >= n) return true if @@primes.index n return false end p=PrimeList.new sq=Math.sqrt(n) while(p.last<=sq) return false if n % (p.getNext)==0 end true end def PrimeList.get(i) PrimeList.gen while @@primes.length<=i @@primes[i] end def PrimeList.getPrimeNear(n) PrimeList.gen until n<@@primes[-1] @@primes[PrimeList.primeIndexNear(n)] end private def PrimeList.primeIndexNear(n) return 0 if n<@@primes[0] return [-1] if n>@@primes[-1] PrimeList.getIndexNear(@@primes,n) end def PrimeList.getIndexNear(list,n) return 0 if list.length==1 if(list.length==2) avg=(list[0]+list[1])/2.0 return 1 if n>avg return 0 end splitAfter=list.size/2 return PrimeList.getIndexNear(list[0..splitAfter],n) if n<list[splitAfter] return splitAfter+1+PrimeList.getIndexNear(list[(splitAfter+1)..-1],n) if n>list[splitAfter+1] avg=(list[splitAfter]+list[splitAfter+1])/2 return splitAfter+1 if n>avg splitAfter end def PrimeList.gen add=@@primes[-1] cands=Set.new(1..(5*add)){|i|2*i+add} theBegin=add+2 theEnd=11*add highest=Math.sqrt(theEnd).to_i upTo=PrimeList.primeIndexNear(highest) upTo-=1 if @@primes[upTo]>highest @@primes[1..upTo].each do |mult| ((theBegin-theBegin%mult)..(theEnd-theEnd%mult + mult)).step(mult){|i|cands.delete i} end @@primes=@@primes+cands.to_a.sort end end
+-//PrimeListdef p10{ var tot=0L var i=0 var p=0 while(p<2000000){ tot+=p p=PrimeList.get(i) i+=1 } println(tot) }object PrimeList{ var myPrimes=Array(2,3,5,7,11,13) def get(i: Int)={ while(i>=myPrimes.length)expand myPrimes(i) } private def expand{ val base=myPrimes.last+2 val highest=base+myPrimes.length*10 val candidates=new Array[Int](1+(highest-base)/2) val limit=Math.sqrt(highest) val filters=myPrimes.takeWhile(_<=limit).dropWhile(_==2) def filterWith(p: Int){ var x=(base.toFloat/p).ceil.toInt*p while(x<=highest){ if(x%2==1)candidates((x-base)/2)=1 x+=p } } filters.foreach(filterWith) var survivors=List[Int]() var i=0 while(i<candidates.length){ if(candidates(i)==0)survivors=(base+2*i)::survivors i+=1 } myPrimes=myPrimes++survivors.reverse } }