/* Factors of an integer (Rosetta code) in Picat. http://rosettacode.org/wiki/Factors_of_an_integer """ Compute the factors of a positive integer. These factors are the positive integers by which the number being factored can be divided to yield a positive integer result. (Though the concepts function correctly for zero and negative integers, the set of factors of zero has countably infinite members, and the factors of negative integers can be obtained from the factors of related positive numbers without difficulty; this task does not require handling of either of these cases). Note that every prime number has two factors: 1 and itself. """ These are all divisors of an integer (i.e. just just the prime factors). This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import v3_utils. % import util. % import cp. main => go. /* for N = 10**15+1 CPU time 1.589 seconds. fs1 = [1,7,11,13,77,91,143,211,241,1001,1477,1687,2161,2321,2651,2743,3133,9091,15127,16247,18557,19201,21931,23771,28093,30173,34463,50851,63637,100001,118183,166397,196651,211211,241241,309023,355957,455971,520801,559361,661063,700007,827281,1300013,1918201,2163161,2190931,3191797,3645607,3915527,4627441,5015681,5728811,5927623,6770413,7271693,9100091,13427407,15336517,19645651,21100211,24100241,24936613,28482103,35109767,40101677,41493361,47392891,50901851,65203853,74474543,109889011,137519557,147701477,168701687,174556291,199374721,216102161,255393463,274302743,313303133,456426971,462286441,521321801,769223077,1208779121,1428557143,1512715127,1787754241,1920119201,2193121931,2809328093,3236005087,4145232361,4734601891,5085150851,6009723733,8461453847,9999900001,15714128573,19665296651,29016626527,33142213237,35596055957,42068066131,45597555971,52080620801,53888020693,61549824583,66106961063,109998900011,319182891797,364564345607,377216144851,430848772081,462748727441,592768227623,677048070413,999000999001,4149377593361,4739336492891,6993006993007,10989010989011,12987012987013,76923076923077,90909090909091,142857142857143,1000000000000001] CPU time 1.218 seconds. fs2 = [1,7,11,13,77,91,143,211,241,1001,1477,1687,2161,2321,2651,2743,3133,9091,15127,16247,18557,19201,21931,23771,28093,30173,34463,50851,63637,100001,118183,166397,196651,211211,241241,309023,355957,455971,520801,559361,661063,700007,827281,1300013,1918201,2163161,2190931,3191797,3645607,3915527,4627441,5015681,5728811,5927623,6770413,7271693,9100091,13427407,15336517,19645651,21100211,24100241,24936613,28482103,35109767,40101677,41493361,47392891,50901851,65203853,74474543,109889011,137519557,147701477,168701687,174556291,199374721,216102161,255393463,274302743,313303133,456426971,462286441,521321801,769223077,1208779121,1428557143,1512715127,1787754241,1920119201,2193121931,2809328093,3236005087,4145232361,4734601891,5085150851,6009723733,8461453847,9999900001,15714128573,19665296651,29016626527,33142213237,35596055957,42068066131,45597555971,52080620801,53888020693,61549824583,66106961063,109998900011,319182891797,364564345607,377216144851,430848772081,462748727441,592768227623,677048070413,999000999001,4149377593361,4739336492891,6993006993007,10989010989011,12987012987013,76923076923077,90909090909091,142857142857143,1000000000000001] CPU time 1.243 seconds. fs3 = [1,7,11,13,77,91,143,211,241,1001,1477,1687,2161,2321,2651,2743,3133,9091,15127,16247,18557,19201,21931,23771,28093,30173,34463,50851,63637,100001,118183,166397,196651,211211,241241,309023,355957,455971,520801,559361,661063,700007,827281,1300013,1918201,2163161,2190931,3191797,3645607,3915527,4627441,5015681,5728811,5927623,6770413,7271693,9100091,13427407,15336517,19645651,21100211,24100241,24936613,28482103,35109767,40101677,41493361,47392891,50901851,65203853,74474543,109889011,137519557,147701477,168701687,174556291,199374721,216102161,255393463,274302743,313303133,456426971,462286441,521321801,769223077,1208779121,1428557143,1512715127,1787754241,1920119201,2193121931,2809328093,3236005087,4145232361,4734601891,5085150851,6009723733,8461453847,9999900001,15714128573,19665296651,29016626527,33142213237,35596055957,42068066131,45597555971,52080620801,53888020693,61549824583,66106961063,109998900011,319182891797,364564345607,377216144851,430848772081,462748727441,592768227623,677048070413,999000999001,4149377593361,4739336492891,6993006993007,10989010989011,12987012987013,76923076923077,90909090909091,142857142857143,1000000000000001] N = factorial(18), N=6402373705728000 CPU time 3.936 seconds. CPU time 3.097 seconds. CPU time 3.204 seconds. */ go ?=> % N = 10**15+1, % N = 76576500, N = 6402373705728000, % factorial(18), % println(n=N), println("factors:"), time(Fs1 = factors(N)), println(len=Fs1.len), % println(fs1=Fs1), println("factors2:"), time(factors2(N,Fs2)), println(len=Fs2.len), % println(fs2=Fs2), println("factors3:"), time(Fs3=factors3(N)), % println(fs3=Fs3), println(len=Fs3.len), nl. go => true. % List comprehension factors(N) = [[D,N // D] : D in 1..N.sqrt.floor, N mod D == 0].flatten.sort_remove_dups. % {{trans|Prolog}} factors2(N,Fs) :- integer(N), N > 0, Fs = findall(F,factors2_(N,F)).sort_remove_dups. factors2_(N,F) :- L = floor(sqrt(N)), between(1,L,X), 0 == N mod X, ( F = X ; F = N // X ). % Loop factors3(N) = Set.keys.sort => Set = new_set(), Set.put(1), Set.put(N), foreach(I in 1..floor(sqrt(N)), N mod I == 0) Set.put(I), Set.put(N//I) end.