2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
+-%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)))).+-%factorprime_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.+-%productfactor(1)->[]; factor(N)->factor(N,prime_iterator(self()),0,math:sqrt(N)). factor(1,_,_,_)->[]; factor(N,Iter,LastPrime,Sqrt) when LastPrime >= Sqrt-> exit(Iter,kill), [N]; factor(N,Iter,_,Sqrt)-> Iter ! next, Next=receive {prime,X}->X end, if N rem Next == 0 -> Small=N div Next, exit(Iter,kill), [Next|factor(Small,prime_iterator(self()),0,math:sqrt(Small))]; true-> factor(N,Iter,Next,Sqrt) end.p5()->p5(2,[]). p5(21,MyFactors)->io:format("~w~n",[product(MyFactors)]); p5(N,MyFactors)-> F=factor(N), p5(N+1,lists:append(lists:subtract(MyFactors,F),F)).product(List)-> lists:foldl(fun(X,Prod)->X*Prod end, 1, List).
+-#PrimeList+-#factorsclass 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+-#Enumerabledef factors(n) return [] if n<2 p=PrimeList.new sq=Math.sqrt(n) while(p.last<=sq) if n % (p.getNext)==0 return [p.last]+factors(n/p.last) end end return [n] enddef p5 fax=[] 2.upto(20) do |i| f=factors i f.uniq.each{|j|fax.push j while fax.count(j)<f.count(j)} end puts fax.product endmodule Enumerable def sum self.inject{|u,v|u+v} end def product self.inject{|u,v|u*v} end def count(ob) self.select{|i|i==ob}.length end def take_while return [] unless yield(self.first) if(self.class==Range) evalPoint=self.first evalPoint=evalPoint.succ while yield(evalPoint.succ) and not evalPoint==self.last return self.first..evalPoint else s=self.to_a upTo=1 upTo+=1 while yield(s[upTo]) and upTo<self.length return self[0...upTo] end end end