De Polignac numbers: Difference between revisions
Content added Content deleted
m (→RPL: highlighted syntax) |
(Added BASIC256 and Chipmunk Basic) |
||
Line 312: | Line 312: | ||
Found 19075 De Polignac numbers up to 500000 |
Found 19075 De Polignac numbers up to 500000 |
||
</pre> |
</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|BASIC256}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vb">arraybase 0 |
|||
maxNumber = 500000 # maximum number we will consider |
|||
maxPower = 20 # maximum powerOf2 < maxNumber |
|||
dim powersOf2(maxPower) # sieve the primes to maxNumber |
|||
dim prime(maxNumber) |
|||
prime[0] = false |
|||
prime[1] = false |
|||
prime[2] = true |
|||
for i = 3 to maxNumber step 2 |
|||
prime[i] = true |
|||
next i |
|||
for i = 4 to maxNumber-1 step 2 |
|||
prime[i] = false |
|||
next i |
|||
rootMaxNumber = sqr(maxNumber) |
|||
for i = 3 to rootMaxNumber step 2 |
|||
if prime[i] then |
|||
i2 = i + i |
|||
for s = i * i to maxNumber step i2 |
|||
prime[s] = false |
|||
next s |
|||
end if |
|||
next i |
|||
# table of powers of 2 greater than 2^0 (up to around 2 000 000) |
|||
# increase the table size if maxNumber > 2 000 000 |
|||
p2 = 1 |
|||
for i = 1 to maxPower-1 |
|||
p2 *= 2 |
|||
powersOf2[i] = p2 |
|||
next i |
|||
# the numbers must be odd and not of the form p + 2^n |
|||
# either p is odd and 2^n is even and hence n > 0 and p > 2 |
|||
# or 2^n is odd and p is even and hence n = 0 and p = 2 |
|||
# n = 0, p = 2 - the only possibility is 3 |
|||
print "First 50 de Polignac numbers:" |
|||
dpCount = 0 |
|||
for i = 1 to 3 step 2 |
|||
p = 2 |
|||
if p + 1 <> i then |
|||
dpCount += 1 |
|||
print rjust(i,5); |
|||
end if |
|||
next i |
|||
# n > 0, p > 2 |
|||
for i = 5 to maxNumber step 2 |
|||
found = false |
|||
p = 1 |
|||
while p <= maxPower and not found and i > powersOf2[p] |
|||
found = prime[i - powersOf2[p]] |
|||
p += 1 |
|||
end while |
|||
if not found then |
|||
dpCount += 1 |
|||
if dpCount <= 50 then |
|||
print rjust(i,5); |
|||
if dpCount mod 10 = 0 then print |
|||
else |
|||
if dpCount = 1000 or dpCount = 10000 then print "The "; rjust(dpCount,5); "th De Polignac number is "; i |
|||
end if |
|||
end if |
|||
next |
|||
print "Found "; dpCount; " De Polignac numbers up to "; maxNumber</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Similar to FreeBASIC entry.</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="qbasic">100 maxnumber = 500000 ' maximum number we will consider |
|||
110 maxpower = 20 ' maximum powerOf2 < maxNumber |
|||
120 dim powersof2(maxpower)' sieve the primes to maxNumber |
|||
130 dim prime(maxnumber) |
|||
140 prime(0) = false |
|||
150 prime(1) = false |
|||
160 prime(2) = true |
|||
170 for i = 3 to maxnumber step 2 |
|||
180 prime(i) = true |
|||
190 next i |
|||
200 for i = 4 to maxnumber step 2 |
|||
210 prime(i) = false |
|||
220 next i |
|||
230 rootmaxnumber = sqr(maxnumber) |
|||
240 for i = 3 to rootmaxnumber step 2 |
|||
250 if prime(i) then |
|||
260 i2 = i+i |
|||
270 for s = i*i to maxnumber step i2 |
|||
280 prime(s) = false |
|||
290 next s |
|||
300 endif |
|||
310 next i |
|||
320 ' table of powers of 2 greater than 2^0 (up to around 2 000 000) |
|||
330 ' increase the table size if maxNumber > 2 000 000 |
|||
340 p2 = 1 |
|||
350 for i = 1 to maxpower |
|||
360 p2 = p2*2 |
|||
370 powersof2(i) = p2 |
|||
380 next i |
|||
390 ' the numbers must be odd and not of the form p + 2^n |
|||
400 ' either p is odd and 2^n is even and hence n > 0 and p > 2 |
|||
410 ' or 2^n is odd and p is even and hence n = 0 and p = 2 |
|||
420 ' n = 0, p = 2 - the only possibility is 3 |
|||
430 print "First 50 de Polignac numbers:" |
|||
440 dpcount = 0 |
|||
450 for i = 1 to 3 step 2 |
|||
460 p = 2 |
|||
470 if p+1 <> i then |
|||
480 dpcount = dpcount+1 |
|||
490 print using "#####";i; |
|||
500 endif |
|||
510 next i |
|||
520 ' n > 0, p > 2 |
|||
530 for i = 5 to maxnumber step 2 |
|||
540 found = false |
|||
550 p = 1 |
|||
560 while p <= maxpower and not found and i > powersof2(p) |
|||
570 found = prime(i-powersof2(p)) |
|||
580 p = p+1 |
|||
590 wend |
|||
600 if not found then |
|||
610 dpcount = dpcount+1 |
|||
620 if dpcount <= 50 then print using "#####";i; |
|||
660 if dpcount = 1000 or dpcount = 10000 then |
|||
670 print : print "The "; |
|||
680 print using "#####";dpcount; |
|||
690 print "th De Polignac number is ";i; |
|||
700 endif |
|||
720 endif |
|||
730 next |
|||
740 print : print chr$(10);"Found ";dpcount;"De Polignac numbers up to ";maxnumber |
|||
750 end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Similar to FreeBASIC entry.</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Line 542: | Line 682: | ||
Const maxPower = 20 ' maximum powerOf2 < maxNumber |
Const maxPower = 20 ' maximum powerOf2 < maxNumber |
||
Dim As Uinteger powersOf2(1 To maxPower) ' sieve the primes to maxNumber |
|||
Dim As Boolean prime(0 To maxNumber) |
Dim As Boolean prime(0 To maxNumber) |
||
Dim As Uinteger powersOf2(1 To maxPower) |
|||
' sieve the primes to maxNumber |
|||
Dim As Integer rootMaxNumber = Sqr(maxNumber) |
Dim As Integer rootMaxNumber = Sqr(maxNumber) |
||
Dim As Integer i, s |
|||
prime(0) = false |
prime(0) = false |
||
prime(1) = false |
prime(1) = false |
||
prime(2) = true |
prime(2) = true |
||
Dim As Integer i, s |
|||
For i = 3 To maxNumber Step 2 |
For i = 3 To maxNumber Step 2 |
||
prime(i) = true |
prime(i) = true |
||
Line 604: | Line 744: | ||
End If |
End If |
||
Next |
Next |
||
Print "Found"; dpCount; " De Polignac numbers up to"; maxNumber |
Print "Found "; dpCount; " De Polignac numbers up to "; maxNumber |
||
Sleep</syntaxhighlight> |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |