Sieve of Eratosthenes: Difference between revisions
faster variant
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
(faster variant) |
||
Line 10,301:
=={{header|jq}}==
{{works with|jq|1.4}}
==Bare Bones==
Short and sweet ...
Line 10,327:
{{out}}
664579
===Enhanced Sieve===
Here is a more economical variant that:
* produces a stream of primes less than or equal to a given integer;
* only records the status of odd integers greater than 3 during the sieving process;
* optimizes the inner loop as described in the task description.
<syntaxhighlight lang=jq>
def primes:
# The array we use for the sieve only stores information for the odd integers greater than 1:
# index integer
# 0 3
# k 2*k + 3
# So if we wish to mark m = 2*k + 3, the relevant index is: m - 3 / 2
def ix:
if . % 2 == 0 then null
else ((. - 3) / 2)
end;
# erase(i) sets .[i*j] to false for odd integral j > i, and assumes i is odd
def erase(i):
((i - 3) / 2) as $k
# Consider relevant multiples:
then (((length * 2 + 3) / i)) as $upper
# ... only consider odd multiples from i onwards
| reduce range(i; $upper; 2) as $j (.;
(((i * $j) - 3) / 2) as $m
| if .[$m] then .[$m] = false else . end);
if . < 2 then []
else (. + 1) as $n
| (($n|sqrt) / 2) as $s
| [range(3; $n; 2)|true]
| reduce (1 + (2 * range(1; $s)) ) as $i (.; erase($i))
| . as $sieve
| 2, (range(3; $n; 2) | select($sieve[ix]))
end ;
def count(s): reduce s as $_ (0; .+1);
count(1e6 | primes)
</syntaxhighlight>
{{output}}
<pre>
78498
</pre>
=={{header|Julia}}==
| |||