Brilliant numbers: Difference between revisions

Content added Content deleted
(Added Rust solution)
(→‎{{header|Phix}}: replaced with C++ translation, much faster even/and with 1e15 limit, even on 32 bit.)
Line 500: Line 500:


=={{header|Phix}}==
=={{header|Phix}}==
{{trans|C++}}
{{libheader|Phix/online}}
{{libheader|Phix/online}}
Replaced with C++ translation; much faster and now goes comfortably to 1e15 even on 32 bit.
You can run this online [http://phix.x10.mx/p2js/brilliant.htm here].
You can run this online [http://phix.x10.mx/p2js/brilliant.htm here].
<!--<lang Phix>(phixonline)-->
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\BrilliantNumbers.exw
-- =================================
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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;">-- binary_search() mods</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)</span>
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">klim</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">plim</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">64</span><span style="color: #0000FF;">?{</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e5</span><span style="color: #0000FF;">}),</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
⚫
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plim</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">glim</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">lp</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">pj</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_primes_by_digits</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lp</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</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;">limit</span><span style="color: #0000FF;">)),</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">*</span><span style="color: #000000;">pj</span><span style="color: #0000FF;"><</span><span style="color: #000000;">limit</span>
<span style="color: #000000;">primes_by_digits</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
⚫
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
⚫
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
⚫
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">primes_by_digits</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">]}</span>
⚫
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span>
⚫
<span style="color: #000000;">p</span><span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
⚫
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
⚫
<span style="color: #008080;">return</span> <span style="color: #000000;">primes_by_digits</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
⚫
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes_by_digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_primes_by_digits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_brilliant</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">countOnly</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">first100</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">brilliant</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">brilliant_numbers</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">primes</span> <span style="color: #008080;">in</span> <span style="color: #000000;">primes_by_digits</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">pow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">digits</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">finish</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">brilliant_numbers</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</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;">start</span> <span style="color: #008080;">to</span> <span style="color: #000000;">finish</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">countOnly</span> <span style="color: #008080;">then</span>
⚫
<span style="color: #004080;">integer</span> <span style="color: #000000;">hij</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">({</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]},</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">finish</span><span style="color: #0000FF;">,</span><span style="color: #000000;">glim</span><span style="color: #0000FF;">))</span>
⚫
<span style="color: #008080;">if</span> <span style="color: #000000;">hij</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</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: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">hij</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span>
<span style="color: #008080;">else</span>
⚫
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">finish</span> <span style="color: #008080;">do</span>
⚫
<span style="color: #004080;">atom</span> <span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</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: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
⚫
<span style="color: #008080;">if</span> <span style="color: #000000;">prod</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">limit</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: #000000;">brilliant</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">prod</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">finish</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brilliant_numbers</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">100</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: #000000;">pow</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">countOnly</span><span style="color: #0000FF;">?</span><span style="color: #000000;">count</span><span style="color: #0000FF;">:</span><span style="color: #000000;">brilliant</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">brilliant_numbers</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brilliant_numbers</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</span><span style="color: #0000FF;">]</span>
⚫
<span style="color: #004080;">sequence</span> <span style="color: #000000;">j100</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brilliant_numbers</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,5d"</span><span style="color: #0000FF;">)</span>
⚫
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">"First 100 brilliant numbers:\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j100</span><span style="color: #0000FF;">})</span>
⚫
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">b100</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">get_brilliant</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">))[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</span><span style="color: #0000FF;">],</span>
⚫
<span style="color: #000000;">first100</span><span style="color: #0000FF;">()</span>
⚫
<span style="color: #000000;">j100</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</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;">"First 100 brilliant numbers:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j100</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">klim</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">pwr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">limit</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;">k</span><span style="color: #0000FF;">),</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes_by_digits</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_brilliant</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes_by_digits</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</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: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span>
<span style="color: #000000;">min_product</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">))),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
⚫
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">pwr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</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;">k</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;">primes</span><span style="color: #0000FF;">)),</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (always is, I think)</span>
<span style="color: #000000;">hp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</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;">k</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;">primes</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</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;">lp</span> <span style="color: #008080;">to</span> <span style="color: #000000;">hp</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p2</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">hp</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">min_product</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">prod</span><span style="color: #0000FF;"><</span><span style="color: #000000;">min_product</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</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: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">min_product</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prod</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">prod</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">lo</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">prod</span><span style="color: #0000FF;"><</span><span style="color: #000000;">hi</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prod</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">p2</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: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">exit</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;">"First brilliant number &gt;= 10^%d is %,d at position %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">min_product</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">})</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: #000000;">pwr</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
⚫
<span style="color: #004080;">integer</span> <span style="color: #000000;">size</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span>
⚫
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">size</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">size</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;">2</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">"First &gt;= %,18d is %,14d%s in the series: %,18d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">total</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">t0</span><span style="color: #0000FF;">)</span>
⚫
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
<!--</lang>-->
{{out}}
{{out}}
<pre>
<pre>
First 100 brilliant numbers:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
961 979 989 1,003 1,007 1,027 1,037 1,067 1,073 1,079
1,081 1,121 1,139 1,147 1,157 1,159 1,189 1,207 1,219 1,241
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1,247 1,261 1,271 1,273 1,333 1,343 1,349 1,357 1,363 1,369
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369



First brilliant number >= 10^1 is 10 at position 4
First >= 10 is 4th in the series: 10
First brilliant number >= 10^2 is 121 at position 11
First >= 100 is 11th in the series: 121
First brilliant number >= 10^3 is 1,003 at position 74
First >= 1,000 is 74th in the series: 1,003
First brilliant number >= 10^4 is 10,201 at position 242
First >= 10,000 is 242nd in the series: 10,201
First brilliant number >= 10^5 is 100,013 at position 2,505
First >= 100,000 is 2,505th in the series: 100,013
First brilliant number >= 10^6 is 1,018,081 at position 10,538
First >= 1,000,000 is 10,538th in the series: 1,018,081
First >= 10,000,000 is 124,364th in the series: 10,000,043
First brilliant number >= 10^7 is 10,000,043 at position 124,364
First >= 100,000,000 is 573,929th in the series: 100,140,049
First brilliant number >= 10^8 is 100,140,049 at position 573,929
First >= 1,000,000,000 is 7,407,841st in the series: 1,000,000,081
First brilliant number >= 10^9 is 1,000,000,081 at position 7,407,841
First >= 10,000,000,000 is 35,547,995th in the series: 10,000,600,009
First brilliant number >= 10^10 is 10,000,600,009 at position 35,547,995
First >= 100,000,000,000 is 491,316,167th in the series: 100,000,000,147
First brilliant number >= 10^11 is 100,000,000,147 at position 491,316,167
First >= 1,000,000,000,000 is 2,409,600,866th in the series: 1,000,006,000,008
First brilliant number >= 10^12 is 1,000,006,000,009 at position 2,409,600,866
First >= 10,000,000,000,000 is 34,896,253,010th in the series: 10,000,000,000,073
First brilliant number >= 10^13 is 10,000,000,000,073 at position 34,896,253,010
First brilliant number >= 10^14 is 100,000,380,000,361 at position 174,155,363,187
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
"3.3s"
</pre>
</pre>
Obviously you don't get the last 4 lines under 32bit, or pwa/p2js.


=={{header|Raku}}==
=={{header|Raku}}==
Retrieved from "https://rosettacode.org/wiki/Brilliant_numbers"