De Polignac numbers: Difference between revisions
De Polignac numbers in FreeBASIC
(Added C++ solution) |
(De Polignac numbers in FreeBASIC) |
||
Line 324:
Ten thousandth: 273,421
</pre>
=={{header|FreeBASIC}}==
{{trans|ALGOL W}}
<syntaxhighlight lang="freebasic">' find some De Polignac numbers - positive odd numbers that can't be
' written as p + 2^n for some prime p and integer n
Const maxNumber = 500000 ' maximum number we will consider
Const maxPower = 20 ' maximum powerOf2 < 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)
prime(0) = false
prime(1) = false
prime(2) = true
Dim As Integer i, s
For i = 3 To maxNumber Step 2
prime(i) = true
Next i
For i = 4 To maxNumber Step 2
prime(i) = false
Next i
For i = 3 To rootMaxNumber Step 2
If prime(i) Then
Dim As Integer 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
Dim As Integer p2 = 1
For i = 1 To maxPower
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
Dim As Uinteger dpCount = 0
For i = 1 To 3 Step 2
Dim As Integer p = 2
If p + 1 <> i Then
dpCount += 1
Print Using "#####"; i;
End If
Next i
' n > 0, p > 2
For i = 5 To maxNumber Step 2
Dim As Boolean found = false
Dim As Integer p = 1
While p <= maxPower And Not found And i > powersOf2(p)
found = prime(i - powersOf2(p))
p += 1
Wend
If Not found Then
dpCount += 1
If dpCount <= 50 Then
Print Using "#####"; i;
If dpCount Mod 10 = 0 Then Print
Elseif dpCount = 1000 Or dpCount = 10000 Then
Print Using "The #####th De Polignac number is ######"; dpCount; i
End If
End If
Next
Print "Found"; dpCount; " De Polignac numbers up to"; maxNumber
Sleep</syntaxhighlight>
{{out}}
<pre>Same as ALGOL W entry.</pre>
=={{header|J}}==
| |||