Task

Write a generator of prime numbers, in order, that will automatically adjust to accommodate the generation of any reasonably high prime.

The routine should demonstrably rely on either:

 Being based on an open-ended counter set to count without upper limit other than system or programming language limits. In this case, explain where this counter is in the code.
 Being based on a limit that is extended automatically. In this case, choose a small limit that ensures the limit will be passed when generating some of the values to be asked for below.
 If other methods of creating an extensible prime generator are used, the algorithm's means of extensibility/lack of limits should be stated.


The routine should be used to:

 Show the first twenty primes.
 Show the primes between 100 and 150.
 Show the number of primes between 7,700 and 8,000.
 Show the 10,000th prime.


Show output on this page.

Note: You may reference code already on this site if it is written to be imported/included, then only the code necessary for import and the performance of this task need be shown. (It is also important to leave a forward link on the referenced tasks entry so that later editors know that the code is used for multiple tasks).

Note 2: If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a system limit, (231 or memory overflow for example), then this may be used as long as an explanation of the limits of the prime generator is also given. (Which may include a link to/excerpt from, language documentation).

Note 3:The task is written so it may be useful in solving the task   Emirp primes   as well as others (depending on its efficiency).





Reference

 Prime Numbers. Website with large count of primes.


' 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