De Polignac numbers: Difference between revisions
Added BASIC256 and Chipmunk Basic
m (→RPL: highlighted syntax) |
(Added BASIC256 and Chipmunk Basic) |
||
Line 312:
Found 19075 De Polignac numbers up to 500000
</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}}==
Line 542 ⟶ 682:
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 Integer rootMaxNumber = Sqr(maxNumber)
Dim As Integer i, s
prime(0) = false
prime(1) = false
prime(2) = true
For i = 3 To maxNumber Step 2
prime(i) = true
Line 604 ⟶ 744:
End If
Next
Print "Found "; dpCount; " De Polignac numbers up to "; maxNumber
Sleep</syntaxhighlight>
{{out}}
| |||