45 lines
1.1 KiB
Text
45 lines
1.1 KiB
Text
def count(s): reduce s as $x (0; .+1);
|
|
|
|
def isSquare:
|
|
(sqrt|floor) as $sqrt
|
|
| . == ($sqrt | .*.);
|
|
|
|
# Input: a positive integer
|
|
# Output: an array, $a, of length .+1 such that
|
|
# $a[$i] is $i if $i is prime, and false otherwise.
|
|
def primeSieve:
|
|
# erase(i) sets .[i*j] to false for integral j > 1
|
|
def erase($i):
|
|
if .[$i] then
|
|
reduce (range(2*$i; length; $i)) as $j (.; .[$j] = false)
|
|
else .
|
|
end;
|
|
(. + 1) as $n
|
|
| (($n|sqrt) / 2) as $s
|
|
| [null, null, range(2; $n)]
|
|
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i));
|
|
|
|
def gcd(a; b):
|
|
# subfunction expects [a,b] as input
|
|
# i.e. a ~ .[0] and b ~ .[1]
|
|
def rgcd: if .[1] == 0 then .[0]
|
|
else [.[1], .[0] % .[1]] | rgcd
|
|
end;
|
|
[a,b] | rgcd;
|
|
|
|
# divisors as an unsorted stream (without calling sqrt)
|
|
def divisors:
|
|
if . == 1 then 1
|
|
else . as $n
|
|
| label $out
|
|
| range(1; $n) as $i
|
|
| ($i * $i) as $i2
|
|
| if $i2 > $n then break $out
|
|
else if $i2 == $n
|
|
then $i
|
|
elif ($n % $i) == 0
|
|
then $i, ($n/$i)
|
|
else empty
|
|
end
|
|
end
|
|
end;
|