The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
+-%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.p3()->io:format("~w~n",[lists:last(factor(600851475143))]).factor(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.
+-#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 enddef p3 puts factors(600851475143)[-1] enddef 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] end
+-//PrimeList+-//factorobject 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 } }def p3 { println(factor(600851475143L).last) }def factor(n: Long):List[Int]={ if(n==1)return List[Int]() val limit=Math.sqrt(n) var i=0 var p=0 while(p<=limit){ p=PrimeList.get(i) if(n%p==0)return p::factor(n/p) i+=1 } List(n.toInt) }