School themes from USSR and EurAsia

[JRace]

10001th prime

Find and show: 10001st prime number
rosettacode.org/wiki/10001th_prime

Okay, you made me think.
I dusted off an old Sieve of Eratosthenes program I had lying around.
Problem is: the original version of the program has no quick-and-easy way to stop when prime 10001 is found.
SO, I tweaked the buffer size so that ONLY 10001 primes will fit.

(Edit: OK, NOW there is a way to catch and print the nth prime: set the "target" constant to be your chosen target.
This ALSO means you can go hog wild and increase the size of the prime flag buffer to any size you want, if the compiler is OK with it, by changing the "size" constant.)

This thing runs so fast that my run times keep coming out at 0.0 seconds, to I've set this version to run the Sieve loop 100 times to give a meaningful run time.

Is it cheating to use a sieve to improve speed?  The RosettaCode rules say nothing about it.  Of course the rules say nothing about speed requirements, either.

Code: (Select All)

Rem DMDScript demo.
Rem Lightly modified to make it easier to change the number of iterations.
Rem QB64 & FreeBASIC (in QB compatibility mode) port
Rem This version is built to find and display the 10,001st prime, per DANILIN's RosettaCode challenge.


Print "Eratosthenes Sieve prime number calculation"

'Const size = 500000
Const size = 52378
Const sizepl = size + 1

Const iters = 100
Dim Shared flags(sizepl) As Integer 'SHARED not needed for QB64

Const true = 1
Const false = 0

Const target = 10001

Print iters; " iterations": Print
starttime = Timer
For iter = 1 To iters
    count = 0
    For i = 0 To size
        flags(i) = true
    Next
    For i = 0 To size
        If flags(i) = true Then
            prime = i + i + 3
            k = i + prime
            While k <= size
                flags(k) = false
                k = k + prime
            Wend
            count = count + 1
            If (count = target) And (printed = false) Then
                Print "Prime "; target; " is: "; prime: Print
                printed = true
            End If
        End If
    Next
Next

elapsedtime = Timer - starttime
Print count; " primes in the range of 3 to "; size + size + 3
Print
Print "elapsed time = ";: Print Using "##.#####"; elapsedtime
Print "time per iteration = ";: Print Using "##.#####"; elapsedtime / iters

'Sleep 'Prevent the program window from closing immediately

Prime 10001 is: 104759
Time for 100 iterations: 0.38477
Time per iteration:        0.00385

(Edited to add: Doh!  I didn't actually show the 10001st prime with this one.  Fixed.)