Totient function: Difference between revisions
→{{header|jq}}
(Added Fōrmulæ solution) |
|||
Line 1,457:
The count of the primes up to 1,000,000 = 78498
The count of the primes up to 10,000,000 = 664579
</pre>
=={{header|jq}}==
{{works with|jq}}
<lang jq>
# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd:
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
[a,b] | _gcd ;
def count(s): reduce s as $x (0; .+1);
def totient:
. as $n
| count( range(0; .) | select( gcd($n; .) == 1) );
# input: determines the maximum via range(0; .)
# and so may be `infinite`
def primes_via_totient:
range(0; .) | select(totient == . - 1);
</lang>
'''The tasks'''
<lang jq>def task:
def task1($n):
range(1;$n)
| totient as $totient
| {i: ., $totient, isprime: ($totient == ( . - 1 ))};
task1(26);
def onepass:
reduce (10000 | primes_via_totient) as $p ({};
if $p < 10000
then .["10^4"] += 1
| if $p < 1000
then .["10^3"] += 1
| if $p < 100
then .["10^2"] += 1
else . end else . end else . end) ;
task, "\nCounts of primes up to the given limits:", onepass</lang>
{{out}}
<pre>
{"i":1,"totient":1,"isprime":false}
{"i":2,"totient":1,"isprime":true}
{"i":3,"totient":2,"isprime":true}
{"i":4,"totient":2,"isprime":false}
{"i":5,"totient":4,"isprime":true}
{"i":6,"totient":2,"isprime":false}
{"i":7,"totient":6,"isprime":true}
{"i":8,"totient":4,"isprime":false}
{"i":9,"totient":6,"isprime":false}
{"i":10,"totient":4,"isprime":false}
{"i":11,"totient":10,"isprime":true}
{"i":12,"totient":4,"isprime":false}
{"i":13,"totient":12,"isprime":true}
{"i":14,"totient":6,"isprime":false}
{"i":15,"totient":8,"isprime":false}
{"i":16,"totient":8,"isprime":false}
{"i":17,"totient":16,"isprime":true}
{"i":18,"totient":6,"isprime":false}
{"i":19,"totient":18,"isprime":true}
{"i":20,"totient":8,"isprime":false}
{"i":21,"totient":12,"isprime":false}
{"i":22,"totient":10,"isprime":false}
{"i":23,"totient":22,"isprime":true}
{"i":24,"totient":8,"isprime":false}
{"i":25,"totient":20,"isprime":false}
Counts of primes up to the given limits:
{"10^4":1229,"10^3":168,"10^2":25}
</pre>
| |||