Legendre prime counting function: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: added a non recursive partial sieve version) |
|||
Line 2,855: | Line 2,855: | ||
</pre> |
</pre> |
||
<small>(It is about 4 times slower under pwa/p2js so output is limited to 10^8, unless you like staring at a blank screen for 52s)</small> |
<small>(It is about 4 times slower under pwa/p2js so output is limited to 10^8, unless you like staring at a blank screen for 52s)</small> |
||
=== Non-recurive partial sieve === |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (for in, tagstart)</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #000080;font-style:italic;">// convenience convert to idx</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">count_primes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">// non-recursive Legendre prime counting function for a range `n`... |
|||
// has O(n^(3/4)/((log n)^2)) time complexity; O(n^(1/2)) space complexity.</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">// can't odd sieve for n less than 3!</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">sqrtn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)),</span> <span style="color: #000080;font-style:italic;">// (actual limit)</span> |
|||
<span style="color: #000000;">mxndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">sqrtn</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">// odds-only limit |
|||
-- |
|||
-- smalls is the current accumulated counts of odd primes 1 to sqrt(n), initialized |
|||
-- to odds-only sieving, ie {0,1,2,3,4...} meaning 0 odd primes to 1, 1 o.p to 3,... |
|||
-- |
|||
-- roughs is the current odd k-rough numbers up to sqrt of range; k = 2 |
|||
-- initialized to all odd positive numbers 1, 3, 5, 7, 9, 11, ... sqrt(n) |
|||
-- |
|||
-- larges is an array of current phi counts for the above roughs... except they are |
|||
-- not strictly `phi`'s since they also include primes, to match `smalls` above! |
|||
-- initialized for current roughs after accounting for the even prime of two... |
|||
-- |
|||
-- composite is a flag array representing odd numbers 1..sqrtn, for sieving. |
|||
-- initialized false, meaning all positive odd numbers are potentially prime |
|||
-- note that this array starts at (and keeps) 1 to match the algorithm even |
|||
-- though 1 is not actually a prime, as 1 is important in computation of phi... |
|||
--</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">smalls</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mxndx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">roughs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mxndx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">larges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_floor_div</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roughs</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">composite</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mxndx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">bp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">// 'current' base prime</span> |
|||
<span style="color: #000000;">nbp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">// number of base primes found </span> |
|||
<span style="color: #000000;">mxri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mxndx</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">// current highest used rough index</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sqri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> <span style="color: #000080;font-style:italic;">// index and square (index-1) limit |
|||
// partial sieve loop, adjusting larges/smalls, compressing larges/roughs...</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">sqri</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">mxndx</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">// partial sieve to square index limit</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">composite</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000080;font-style:italic;">// cull from composite so they will never be found again</span> |
|||
<span style="color: #000000;">composite</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">// cull bp and multiples</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sqri</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">mxndx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #000000;">bp</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">composite</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000080;font-style:italic;">// partial sieving to current base prime is now completed! |
|||
// now adjust `larges` for latest partial sieve pass...</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ori</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">// compress input rough index(k) to output one</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span> <span style="color: #008080;">in</span> <span style="color: #000000;">roughs</span> <span style="color: #008080;">to</span> <span style="color: #000000;">mxri</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">// q is not necessarily prime but may be a product of primes not yet |
|||
// culled by partial sieving (saves ops cmprd to recursive Legendre) |
|||
// skip over values of `q` already culled in the last partial sieve:</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">qi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000080;font-style:italic;">// index of always odd q!</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">composite</span><span style="color: #0000FF;">[</span><span style="color: #000000;">qi</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000080;font-style:italic;">// since `q` cannot be equal to bp due to cull of bp and above skip;</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bp</span><span style="color: #0000FF;">*</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">// `d` is odd product of some combination of odd primes! |
|||
// the following computation is essential to the algorithm's speed, |
|||
// see the Nim entry for the full details of how this works</span> |
|||
<span style="color: #000000;">dadj</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">sqrtn</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">larges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)]-</span><span style="color: #000000;">nbp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #0000FF;">:</span> <span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">))])</span> |
|||
<span style="color: #000000;">ori</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">larges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ori</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">larges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">dadj</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nbp</span> <span style="color: #000080;font-style:italic;">// base primes count over subtracted! |
|||
// eliminate rough values that have been culled in partial sieve: |
|||
// note that `larges` and `roughs` indices relate to each other!</span> |
|||
<span style="color: #000000;">roughs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ori</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mxndx</span> <span style="color: #000080;font-style:italic;">// and adjust `smalls` for latest partial sieve pass... |
|||
// this is faster than recounting over the `composite` array for each loop...</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=(</span><span style="color: #000000;">sqrtn</span><span style="color: #0000FF;">/</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)||</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">bp</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">// k always odd! |
|||
// `c` is correction from current count to desired count... |
|||
// `e` is end limit index no correction is necessary for current cull...</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)]-</span><span style="color: #000000;">nbp</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">k</span><span style="color: #0000FF;">*</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">e</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">-- smalls[m+1] -= c -- (grr, js! [I have a plan, working on it])</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">c</span> |
|||
<span style="color: #000080;font-style:italic;">-- m -= 1</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">nbp</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">// increase number of found base primes</span> |
|||
<span style="color: #000000;">mxri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ori</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">// advance rough index for later</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">bp</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #000000;">sqri</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)*(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000080;font-style:italic;">// now `smalls` is a LUT of odd prime accumulated counts for all odd primes; |
|||
// `roughs` is exactly the "k-roughs" up to the sqrt of range with `k` (erm, |
|||
// mxri?) the index of the next prime above the quad root of the range; |
|||
// `larges` is the partial prime counts for each of the `roughs` values... |
|||
// note that `larges` values include the count of the odd base primes!!! |
|||
// - and `composite` is never used again! |
|||
// the following does the top-most "phi tree" calculation: |
|||
// the answer to here is all valid `phis`, combined here by subtraction, |
|||
// + compensate for included odd base prime counts over subracted above:</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">larges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">larges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..</span><span style="color: #000000;">mxri</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #0000FF;">+</span> <span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">((</span><span style="color: #000000;">mxri</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">nbp</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))*</span><span style="color: #000000;">mxri</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">// include the only even prime, ie 2 |
|||
// This loop adds the counts due to the products of the `roughs` primes, |
|||
// of which we only use two different ones at a time, as all the |
|||
// combinations with lower primes than the cube root of the range have |
|||
// already been computed and included with the previous major loop... |
|||
// see text description in the Nim entry for how this works...</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span> <span style="color: #008080;">in</span> <span style="color: #000000;">roughs</span> <span style="color: #008080;">from</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">// for all `roughs` (now prime) bar '1':</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">// `m` is the `p` quotient |
|||
// so that the end limit `e` can be calculated based on `n`/(`p`^2)</span> |
|||
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">p</span><span style="color: #0000FF;">))+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">nbp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #000080;font-style:italic;">// the following test is equivalent to non-splitting optmization:</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">e</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">ri</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">// quit when no more pairs! - aka stop |
|||
// at about `p` of cube root of range!</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">e</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">// for all `roughs` greater than `p` to limit:</span> |
|||
<span style="color: #000000;">result</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">smalls</span><span style="color: #0000FF;">[</span><span style="color: #000000;">half</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">roughs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]))];</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000080;font-style:italic;">// compensate for all the extra base prime counts just added!</span> |
|||
<span style="color: #000000;">result</span> <span style="color: #0000FF;">-=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)*(</span><span style="color: #000000;">nbp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">result</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">expected</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">168</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1229</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9592</span><span style="color: #0000FF;">,</span><span style="color: #000000;">78498</span><span style="color: #0000FF;">,</span><span style="color: #000000;">664579</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5761455</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">50847534</span><span style="color: #0000FF;">,</span><span style="color: #000000;">455052511</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4118054813</span><span style="color: #0000FF;">,</span><span style="color: #000000;">37607912018</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">346065536839</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3204941750802</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">11</span><span style="color: #0000FF;">:</span><span style="color: #000000;">14</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (sp: keep js under 2s)</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">count_primes</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">==</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" (%s)"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"10^%d = %d%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nTook %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
10^0 = 0 |
|||
10^1 = 4 |
|||
10^2 = 25 |
|||
10^3 = 168 |
|||
10^4 = 1229 |
|||
10^5 = 9592 |
|||
10^6 = 78498 |
|||
10^7 = 664579 |
|||
10^8 = 5761455 |
|||
10^9 = 50847534 |
|||
10^10 = 455052511 (0.3s) |
|||
10^11 = 4118054813 (1.7s) |
|||
10^12 = 37607912018 (7.9s) |
|||
10^13 = 346065536839 (40.8s) |
|||
10^14 = 3204941750802 (3 minutes and 44s) |
|||
Took 3 minutes and 44s |
|||
</pre> |
|||
About 15 times slower than Julia on the same box (gulp, earmarked for further investigation in 2.0.0).<br> |
|||
[At the last minute, I nicked the idea of using a simple bool array instead of those bit-fields from Julia.]<br> |
|||
A copy of this code [up to 1e9] has also found it's way into tests\t68forin.exw |
|||
=={{header|Picat}}== |
=={{header|Picat}}== |