(06-06-2022, 03:15 PM)DANILIN Wrote: 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 ?! ?!

(06-06-2022, 03:15 PM)DANILIN Wrote: 10001th prime

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

(06-08-2022, 02:49 PM)bplus Wrote: @JRACE

This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop

But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.

Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.

Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.

Quote:10001th prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.


10001th prime
Task

Find and show on this page the 10001st prime number.