Sieve of Pritchard: Difference between revisions
Added FreeBasic
(New post.) |
(Added FreeBasic) |
||
Line 334:
50847534 primes up to 1000000000 found in 2339.566 ms using array w[163588196]
</pre>
=={{header|FreeBASIC}}==
{{trans|Wren}}
<syntaxhighlight lang="vb">#define min(a, b) iif((a) < (b), (a), (b))
Sub sieveOfPritchard(limit As Uinteger, imprime As Boolean)
Dim As Boolean members(1 To limit + 1)
members(1) = True
Dim As Uinteger ub = Ubound(members)
Dim As Uinteger stepLength = 1
Dim As Uinteger prime = 2
Dim As Uinteger rtlim = Sqr(limit)
Dim As Uinteger nlimit = 2
Dim As Integer primes()
Dim As Integer i, cont = 0
While prime <= rtlim
If stepLength < limit Then
For w As Integer = 1 To ub
If members(w) Then
Dim As Integer n = w + stepLength
While n <= nlimit
members(n) = True
n += stepLength
Wend
End If
Next
stepLength = nlimit
End If
Dim As Uinteger np = 5
Dim As Boolean mcpy(ub)
For i = 1 To ub
mcpy(i) = members(i)
Next
For i = 1 To ub
If mcpy(i) Then
If np = 5 And i > prime Then np = i
Dim As Uinteger n = prime * i
If n > limit Then Exit For there.
members(n) = False
End If
Next
If np < prime Then Exit While
cont += 1
Redim Preserve primes(cont)
primes(cont) = prime
prime = Iif(prime = 2, 3, np)
nlimit = min(stepLength * prime, limit)
Wend
Dim As Integer newPrimes(ub)
For i = 2 To ub
If members(i) Then newPrimes(i) = i
Next
cont = 0
For i = 1 To Ubound(primes)
If imprime Then Print primes(i);
cont += 1
Next
For i = 1 To ub
If newPrimes(i) Then
cont += 1
If imprime Then Print i;
End If
Next
If Not imprime Then Print !"\nNumber of primes up to "; limit; ":"; cont
End Sub
sieveOfPritchard(150, True)
sieveOfPritchard(1e6, False)
Sleep</syntaxhighlight>
{{out}}
<pre> 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149
Number of primes up to 1000000: 78498</pre>
=={{header|J}}==
| |||