101 lines
2.6 KiB
Plaintext
101 lines
2.6 KiB
Plaintext
' FB 1.05.0
|
|
|
|
Enum SieveLimitType
|
|
number
|
|
between
|
|
countBetween
|
|
End Enum
|
|
|
|
Sub printPrimes(low As Integer, high As Integer, slt As SieveLimitType)
|
|
If high < low OrElse low < 1 Then Return ' too small
|
|
If slt <> number AndAlso slt <> between AndAlso slt <> countBetween Then Return
|
|
If slt <> number AndAlso (low < 2 OrElse high < 2) Then Return
|
|
If slt <> number AndAlso high > 1000000000 Then Return ' too big
|
|
If slt = number AndAlso high > 50000000 Then Return ' too big
|
|
Dim As Integer n
|
|
If slt = number Then
|
|
n = 20 * high '' big enough to accomodate 50 million primes to which this procedure is limited
|
|
Else
|
|
n = high
|
|
End If
|
|
Dim a(2 To n) As Boolean '' only uses 1 byte per element
|
|
For i As Integer = 2 To n : a(i) = True : Next '' set all elements to True to start with
|
|
Dim As Integer p = 2, q
|
|
' mark non-prime numbers by setting the corresponding array element to False
|
|
|
|
Do
|
|
For j As Integer = p * p To n Step p
|
|
a(j) = False
|
|
Next j
|
|
' look for next True element in array after 'p'
|
|
q = 0
|
|
For j As Integer = p + 1 To Sqr(n)
|
|
If a(j) Then
|
|
q = j
|
|
Exit For
|
|
End If
|
|
Next j
|
|
If q = 0 Then Exit Do
|
|
p = q
|
|
Loop
|
|
|
|
Select Case As Const slt
|
|
Case number
|
|
Dim count As Integer = 0
|
|
For i As Integer = 2 To n
|
|
If a(i) Then
|
|
count += 1
|
|
If count >= low AndAlso count <= high Then
|
|
Print i; " ";
|
|
End If
|
|
If count = high Then Exit Select
|
|
End If
|
|
Next
|
|
|
|
Case between
|
|
For i As Integer = low To high
|
|
If a(i) Then
|
|
Print i; " ";
|
|
End if
|
|
Next
|
|
|
|
Case countBetween
|
|
Dim count As Integer = 0
|
|
For i As Integer = low To high
|
|
If a(i) Then count += 1
|
|
Next
|
|
Print count;
|
|
|
|
End Select
|
|
Print
|
|
End Sub
|
|
|
|
Print "The first 20 primes are :"
|
|
Print
|
|
printPrimes(1, 20, number)
|
|
Print
|
|
Print "The primes between 100 and 150 are :"
|
|
Print
|
|
printPrimes(100, 150, between)
|
|
Print
|
|
Print "The number of primes between 7700 and 8000 is :";
|
|
printPrimes(7700, 8000, countBetween)
|
|
Print
|
|
Print "The 10000th prime is :";
|
|
Dim t As Double = timer
|
|
printPrimes(10000, 10000, number)
|
|
Print "Computed in "; CInt((timer - t) * 1000 + 0.5); " ms"
|
|
Print
|
|
Print "The 1000000th prime is :";
|
|
t = timer
|
|
printPrimes(1000000, 1000000, number)
|
|
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
|
|
Print
|
|
Print "The 50000000th prime is :";
|
|
t = timer
|
|
printPrimes(50000000, 50000000, number)
|
|
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
|
|
Print
|
|
Print "Press any key to quit"
|
|
Sleep
|