School themes from USSR and EurAsia

[JRace]

10001th prime

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

qbasic

Code: (Select All)

max = 10001: n=0: s=1 ' PRIMES.bas
While n <= max ' 10001 104743 3 seconds
    f=0
    For j=2 To s^0.5
        If s Mod j = 0 Then f=1
    Next
    If f=0 Then n = n+1
    s = s+1
Wend
Print n-1, s-1

Python

Code: (Select All)

import time; max=10001; n=1; p=1; # PRIMES russian DANILIN
while n<=max: # 10001 104743 5 seconds
    f=0; j=2 # rextester.com/AHEH3087
    while f < 1:
        if j >= int(p**0.5):
            f=2
        if p % j == 0:
            f=1
        j+=1
    if f != 1:
        n+=1;
        #print(n,p);           
    p+=2
print(n-1,p-2)
print(time.perf_counter())

C#

Code: (Select All)

using System; using System.Text; // PRIMEQ.cs
namespace p10001 // 1 second  10001  104743
{ class Program // rextester.com/YXNR89875
    { static void Main(string[] args)
        { int max=10001; int n=1; int p=1; int f; int j;
            while (n <= max)
            { f=0; j=2;
                while (f < 1)
                { if (j >= Convert.ToInt32(Math.Pow(p,0.5)))
                    { f=2; }
                  if (p % j == 0) { f=1; }
                  j++;
                }
                if (f != 1) { n++; } // Console.WriteLine("{0} {1}", n, p);
                p++;
            }
            Console.Write("{0} {1}", n-1, p-1);
            Console.ReadKey();
}}}

qb64

Code: (Select All)

max=10001: n=1: p=0: t=Timer ' PRIMES.bas
While n <= max ' 10001 104743 0.35 seconds
    f=0: j=2
    While f < 1
        If j >= p^0.5 Then f=2
        If p Mod j = 0 Then f=1
        j=j+1
    Wend
    If f <> 1 Then n=n+1: ' Print n, p
    p=p+1
Wend
Print n-1, p-1, Timer-t

Your Answers ?! ?!

That's pretty much the way I would do it, so no major changes, but....
What stands out to me is that the value of p does not change within the inner loop, therefore repeating the exponential operation "p ^ 0.5" within the inner loop is slowing the program down.  Moving "p ^ 0.5" to the outer loop doubles the speed of the program:

Code: (Select All)

'JRace's results:
'Original version: 10001   104743  .21875
'This version:     10001   104743  .109375
max = 10001: n = 1: p = 0: t = Timer ' PRIMES.bas
While n <= max ' 10001 104743 0.35 seconds
    f = 0: j = 2
    pp = p ^ 0.5 'NEW VAR: move exponentiation here, to outer loop
    While f < 1
        'If j >= p ^ 0.5 Then f = 2 'original line
        'NOTE: p does not change in this loop,
        '      therefore p^0.5 doesn't change;
        '      moving p^0.5 to the outer loop will eliminate a lot of FP math)
        If j >= pp Then f = 2 'new version with exponentiation relocated
        If p Mod j = 0 Then f = 1
        j = j + 1
    Wend
    If f <> 1 Then n = n + 1: ' Print n, p
    p = p + 1
Wend
Print n - 1, p - 1, Timer - t

I'm sure the other versions of the program will also give much better times if you make similar changes to their inner loops.