Strong and weak primes: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
m (→{{header|Phix}}: syntax coloured, removed deprecated @=, made better use of builtins, plus some other minor tidying) |
||
Line 1,799: | Line 1,799: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(phixonline)--> |
|||
Using [[Extensible_prime_generator#Phix]] |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<lang Phix>while sieved<10_000_000 do add_block() end while |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">strong</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">weak</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
sequence {strong, weak} @= {} |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">get_maxprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e14</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (ie idx of primes < (sqrt(1e14)==1e7), bar 1st)</span> |
|||
for i=2 to abs(binary_search(10_000_000,primes))-1 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span> |
|||
integer p = primes[i], |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,(</span><span style="color: #7060A8;">get_prime</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: #7060A8;">get_prime</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;">2</span><span style="color: #0000FF;">)</span> |
|||
c = compare(p,(primes[i-1]+primes[i+1])/2) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">strong</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">p</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if c=+1 then strong &= p |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">weak</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">p</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
elsif c=-1 then weak &= p |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end if |
|||
<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;">"The first thirty six strong primes: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">strong</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">36</span><span style="color: #0000FF;">],</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
|||
end for |
|||
<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;">"The first thirty seven weak primes: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span> <span style="color: #000000;">weak</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">37</span><span style="color: #0000FF;">],</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
|||
printf(1,"The first 36 strong primes:") ?strong[1..36] |
|||
<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;">"There are %,d strong primes below %,d and %,d below %,d\n"</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;">1e6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">strong</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e6</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">strong</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1e7</span><span style="color: #0000FF;">})</span> |
|||
printf(1,"The first 37 weak primes:") ?weak[1..37] |
|||
<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;">"There are %,d weak primes below %,d and %,d below %,d\n"</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;">1e6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">weak</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e6</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span> <span style="color: #000000;">weak</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1e7</span><span style="color: #0000FF;">})</span> |
|||
printf(1,"%,7d strong primes below 1,000,000\n",abs(binary_search(1_000_000,strong))-1) |
|||
<!--</lang>--> |
|||
printf(1,"%,7d strong primes below 10,000,000\n",length(strong)) |
|||
printf(1,"%,7d weak primes below 1,000,000\n",abs(binary_search(1_000_000,weak))-1) |
|||
printf(1,"%,7d weak primes below 10,000,000\n",length(weak))</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre style="font-size: 11px"> |
|||
The first |
The first thirty six strong primes: 11, 17, 29, 37, ..., 397, 419, 431, 439 |
||
The first |
The first thirty seven weak primes: 3, 7, 13, 19, ..., 359, 383, 389, 401 |
||
There are 37,723 strong primes below 1,000,000 and 320,991 below 10,000,000 |
|||
There are 37,780 weak primes below 1,000,000 and 321,750 below 10,000,000 |
|||
37,780 weak primes below 1,000,000 |
|||
321,750 weak primes below 10,000,000 |
|||
</pre> |
</pre> |
||