77 lines
3.9 KiB
Raku
77 lines
3.9 KiB
Raku
|
# 20210325 Raku programming solution
|
|||
|
|
|
|||
|
|
my @multiplier = ( 1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11 );
|
|||
|
|
|
|||
|
|
sub circumfix:<ā ā>{ $^n.floor }; sub prefix:<ā>{ $^n.sqrt }; # just for fun
|
|||
|
|
|
|||
|
|
sub SQUFOF ( \š ) {
|
|||
|
|
|
|||
|
|
return 1 if š.is-prime; # if n is prime return 1
|
|||
|
|
return āš if āš == Int(āš); # if n is a perfect square return āš
|
|||
|
|
|
|||
|
|
for @multiplier -> \š {
|
|||
|
|
my \Pā = $ = ā ā(š*š) ā; # P[0]=floor(āN)
|
|||
|
|
my \Qā = $ = 1 ; # Q[0]=1
|
|||
|
|
my \Q = $ = š*š - PāĀ²; # Q[1]=N-P[0]^2 & Q[i]
|
|||
|
|
my \Pāįµ£āįµ„ = $ = Pā; # P[i-1] = P[0]
|
|||
|
|
my \Qāįµ£āįµ„ = $ = Qā; # Q[i-1] = Q[0]
ā
|
|||
|
|
my \P = $ = 0; # P[i]
|
|||
|
|
my \Qāāāā = $ = 0; # P[i+1]
|
|||
|
|
my \b = $ = 0; # b[i]
|
|||
|
|
# i = 1
|
|||
|
|
repeat until āQ == Int(āQ) { # until Q[i] is a perfect square
==
|
|||
|
|
b = āā ā(š*š) + Pāįµ£āįµ„ ā / Q ā; # floor(floor(āN+P[i-1])/Q[i])
ā
|
|||
|
|
P = b*Q - Pāįµ£āįµ„; # P[i]=b*Q[i]-P[i-1]
|
|||
|
|
Qāāāā = Qāįµ£āįµ„ + b*(Pāįµ£āįµ„ - P); # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
ā
|
|||
|
|
( Qāįµ£āįµ„, Q, Pāįµ£āįµ„ ) = Q, Qāāāā, P; # i++
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
b = ā ā ā(š*š)+P ā / Q ā; # b=floor((floor(āN)+P[i])/Q[0])
ā
|
|||
|
|
Pāįµ£āįµ„ = b*Qā - P; # P[i-1]=b*Q[0]-P[i]
ā
|
|||
|
|
Q = ( š*š - Pāįµ£āįµ„Ā² )/Qā; # Q[1]=(N-P[0]^2)/Q[0] & Q[i]
|
|||
|
|
Qāįµ£āįµ„ = Qā; # Q[i-1] = Q[0]
ā
|
|||
|
|
# i = 1
|
|||
|
|
loop { # repeat
|
|||
|
|
b = ā ā ā(š*š)+Pāįµ£āįµ„ ā / Q ā; # b=floor(floor(āN)+P[i-1])/Q[i])
ā
|
|||
|
|
P = b*Q - Pāįµ£āįµ„; # P[i]=b*Q[i]-P[i-1]
|
|||
|
|
Qāāāā = Qāįµ£āįµ„ + b*(Pāįµ£āįµ„ - P); # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
ā
|
|||
|
|
last if (P == Pāįµ£āįµ„); # until P[i+1]=P[i]
|
|||
|
|
( Qāįµ£āįµ„, Q, Pāįµ£āįµ„ ) = Q, Qāāāā, P; # i++
|
|||
|
|
}
|
|||
|
|
given š gcd P { return $_ if $_ != 1|š }
|
|||
|
|
} # gcd(N,P[i]) (if != 1 or N) is a factor of N, otherwise try next k
|
|||
|
|
return 0 # give up
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
race for (
|
|||
|
|
11111, # wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Example
|
|||
|
|
4558849, # example from talk page
|
|||
|
|
# all of the rest are taken from the FreeBASIC entry
|
|||
|
|
2501,12851,13289,75301,120787,967009,997417,7091569,13290059,
|
|||
|
|
42854447,223553581,2027651281,11111111111,100895598169,1002742628021,
|
|||
|
|
# time hoarders
|
|||
|
|
60012462237239, # = 6862753 * 8744663 15s
|
|||
|
|
287129523414791, # = 6059887 * 47381993 80s
|
|||
|
|
11111111111111111, # = 2071723 * 5363222357 2m
|
|||
|
|
384307168202281507, # = 415718707 * 924440401 5m
|
|||
|
|
1000000000000000127, # = 111756107 * 8948056861 12m
|
|||
|
|
9007199254740931, # = 10624181 * 847801751 17m
|
|||
|
|
922337203685477563, # = 110075821 * 8379108103 41m
|
|||
|
|
314159265358979323, # = 317213509 * 990371647 61m
|
|||
|
|
1152921505680588799, # = 139001459 * 8294312261 93m
|
|||
|
|
658812288346769681, # = 62222119 * 10588072199 112m
|
|||
|
|
419244183493398773, # = 48009977 * 8732438749 135m
|
|||
|
|
1537228672809128917, # = 26675843 * 57626245319 254m
|
|||
|
|
# don't know how to handle this one
|
|||
|
|
# for 1e-323, 1e-324 { my $*TOLERANCE = $_ ;
|
|||
|
|
# say 4611686018427387877.sqrt ā
4611686018427387877.sqrt.Int }
|
|||
|
|
# skip the perfect square check and start k with 3 to get the following
|
|||
|
|
# 4611686018427387877, # = 343242169 * 13435662733 217m
|
|||
|
|
) -> \data {
|
|||
|
|
given data.&SQUFOF {
|
|||
|
|
when 0 { say "The number ", data, " is not factored." }
|
|||
|
|
when 1 { say "The number ", data, " is a prime." }
|
|||
|
|
default { say data, " = ", $_, " * ", data div $_.Int }
|
|||
|
|
}
|
|||
|
|
}
|