Nth prime number in CSharp

By Oct 26, 2016

Description:

Here you will find an algorithm and the corresponding CSHARP program, determining the nth prime number, for n rather large natural integers.

Preferencesoft

Usually the method used to determine the n-th prime integer is the Sieve method. But often the prime numbers found, are stored in memory.

It keeps getting the nth prime when n is large enough.

My algorithm is to consider only the numbers not divisible by 2, 3, 5, 7, 11, 13 to sieve, rather than the primes found, as in article Simple primality test in C# we use a displacement table to browse all integers not divisible by 2, 3, 5, 7, 11 13. The divisibility by 2, 3, 5, 7, 11, 13 is periodic and is repeated at the end of p = 2x3x5x7x11x13.

We therefore declare an array of p = 30030 of unsigned long integer and we go from page to page until a counter indicates the nth prime.

For the first page, we use a classical sieve method, because we eliminate the multiple page 2, 3, 5, 7, 11 and 13 and thereby some primes are absent.

For the execution time, the time required to obtain the 562229227th prime number (=12480163177) is about 3 minutes with a surface pro 4.
And to get the 999999999th prime number (=22801763477) is about 6 minutes and 50 seconds.

Output

using System;
 
namespace KthPrimeNumber
{
    class Program
    {
        static ulong NthPrime(ulong n)
        {
            // GenerateDivisibilityTable(13, 1);
            int[] step ={
                16,2,4,6,2,6,4,2,4,6,6,2,6,4,
                2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,
                2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,
                4,6,2,10,6,6,6,2,6,4,2,6,4,14,4,
                2,4,6,8,6,10,2,4,6,2,6,6,6,4,6,
                2,6,4,8,10,2,10,2,4,2,4,6,8,4,2,
                4,12,8,4,2,6,4,6,12,2,4,2,12,6,4,
                6,6,6,2,6,10,2,4,6,2,6,6,4,2,10,
                2,10,2,4,6,6,2,6,6,4,6,8,6,4,2,
                6,4,6,8,4,2,6,4,8,6,4,8,4,6,8,
                10,2,10,2,6,4,2,4,2,10,2,10,2,4,2,
                4,14,4,2,4,6,6,2,6,4,8,10,8,4,2,
                4,6,8,6,4,6,6,6,2,6,6,4,2,4,6,
                2,10,2,4,2,10,2,10,2,6,4,8,6,4,2,
                4,6,6,8,4,2,6,10,8,4,2,6,4,8,10,
                6,2,4,8,6,6,4,2,4,6,2,6,4,6,2,
                10,12,2,4,2,4,6,2,6,4,2,4,12,2,6,
                6,10,6,8,4,2,4,2,4,8,6,12,4,6,2,
                12,4,2,4,6,8,4,2,4,2,12,10,2,4,2,
                4,6,2,10,2,4,6,8,6,4,2,6,4,6,8,
                4,6,2,4,8,6,4,6,2,4,6,2,6,6,4,
                6,6,8,6,4,2,10,2,10,2,4,2,10,2,6,
                4,2,10,6,2,6,4,2,6,4,6,8,6,4,2,
                12,10,6,2,4,6,2,12,4,2,4,8,6,4,2,
                4,2,10,2,10,6,2,4,6,2,6,4,2,10,6,
                2,6,4,12,6,8,6,4,2,4,8,6,4,6,2,
                4,6,8,6,6,4,6,2,6,4,2,4,2,10,12,
                2,4,12,2,6,4,2,4,6,6,2,12,6,4,18,
                2,4,2,4,8,6,4,6,2,4,8,6,6,4,2,
                4,6,2,6,4,2,4,12,2,12,6,4,6,2,6,
                4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,
                2,4,14,4,6,2,10,2,6,6,4,2,10,2,10,
                2,4,14,10,2,4,2,4,6,2,6,10,6,6,2,
                10,2,6,4,6,8,4,2,4,6,8,6,10,2,4,
                6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,
                10,6,2,4,6,8,4,2,4,12,2,6,4,2,6,
                4,6,12,2,4,2,4,8,6,4,6,2,10,2,6,
                10,6,6,2,6,4,2,4,2,10,2,12,4,6,6,
                2,12,4,6,6,2,6,4,2,6,4,14,4,2,6,
                4,8,6,4,6,2,4,6,8,6,6,10,2,6,4,
                6,2,10,2,10,2,4,2,4,8,6,4,2,4,6,
                6,8,4,8,4,6,8,4,2,4,2,12,6,4,6,
                6,6,2,6,6,4,2,4,6,2,6,6,4,2,10,
                2,10,2,6,4,6,2,6,4,2,4,6,14,4,2,
                6,10,8,4,2,4,2,4,8,10,8,4,8,6,10,
                2,4,6,2,6,4,6,2,10,2,10,2,4,2,4,
                6,8,4,2,4,6,6,2,6,6,6,10,8,4,2,
                4,6,8,6,4,8,4,6,2,6,6,4,2,4,6,
                12,2,4,2,10,2,10,2,4,2,4,8,10,2,4,
                6,8,6,4,2,6,4,6,8,4,8,4,8,6,4,
                6,2,4,6,2,6,6,4,6,6,2,6,6,4,2,
                10,12,2,4,2,4,6,2,6,4,2,16,2,6,4,
                2,10,6,8,4,2,4,2,12,6,10,2,4,6,2,
                12,4,2,4,8,6,4,2,4,2,12,10,6,2,4,
                6,2,6,4,2,4,6,6,2,6,4,2,10,6,8,
                10,2,4,8,6,4,6,2,4,6,2,6,6,6,4,
                6,8,4,2,4,2,10,12,2,4,2,10,2,6,4,
                2,4,6,6,2,10,2,6,4,14,6,4,2,4,8,
                10,6,2,4,6,2,6,6,4,2,4,8,6,4,2,
                4,12,2,12,4,2,4,6,2,6,4,2,10,6,2,
                6,4,8,4,6,8,4,2,4,2,4,14,4,6,2,
                10,8,6,4,2,4,6,2,10,2,4,2,12,10,2,
                4,6,6,2,6,4,6,6,6,2,6,6,6,4,6,
                12,2,4,6,8,6,10,2,4,8,6,6,4,2,4,
                6,2,6,4,2,6,10,2,10,2,6,4,6,8,4,
                6,12,2,6,4,2,6,4,6,12,2,4,2,4,14,
                4,6,2,4,6,2,6,10,2,10,2,6,4,2,4,
                12,2,10,2,4,6,6,2,6,6,4,6,6,2,10,
                2,6,4,6,8,4,2,6,4,8,6,4,6,2,4,
                6,8,6,4,2,10,2,6,4,2,6,10,2,10,6,
                2,4,8,6,4,2,4,6,6,2,6,4,8,4,6,
                8,4,2,4,2,4,8,6,4,6,12,2,6,6,4,
                6,6,2,6,4,2,4,2,10,2,12,6,4,6,2,
                10,2,4,6,6,8,4,2,6,18,4,2,4,2,4,
                8,10,6,2,4,8,6,6,6,4,6,2,6,4,6,
                2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,
                6,8,6,6,4,6,8,4,2,4,2,12,6,4,12,
                6,2,6,6,4,2,4,6,8,6,4,2,10,2,10,
                2,4,2,4,6,2,10,2,4,6,8,6,4,2,6,
                4,6,8,4,6,2,4,8,6,4,8,4,6,2,6,
                10,6,6,2,6,6,4,2,10,2,10,2,4,2,4,
                6,8,4,2,10,6,2,6,4,2,6,10,8,4,2,
                4,14,6,4,6,2,4,6,2,12,4,2,4,8,10,
                2,4,2,10,2,10,6,2,4,8,6,4,2,4,6,
                6,2,6,4,2,10,6,8,6,6,4,8,6,4,6,
                2,4,6,2,6,6,6,4,6,2,6,4,2,4,2,
                10,12,2,4,2,10,2,6,4,2,4,12,2,10,2,
                10,14,4,2,4,2,4,8,6,10,2,4,6,2,12,
                4,2,4,6,2,6,4,2,4,14,12,4,2,4,6,
                2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,
                4,6,2,4,14,4,6,2,10,2,6,6,4,2,4,
                6,12,2,4,2,12,10,2,4,2,10,2,6,4,6,
                6,6,2,6,4,2,6,4,6,8,6,4,6,8,16,
                2,4,6,2,6,6,4,2,4,8,6,4,2,6,10,
                2,10,2,4,2,4,6,8,4,2,16,2,6,4,8,
                4,6,12,2,4,2,4,8,6,4,6,2,4,6,8,
                10,2,4,6,2,6,4,2,4,2,10,2,10,2,4,
                6,6,2,6,6,4,6,6,2,6,6,6,4,6,12,
                2,6,4,8,6,4,6,2,4,14,6,4,2,10,2,
                6,4,2,4,2,10,2,10,2,6,4,8,6,4,6,
                6,6,2,6,4,8,4,6,8,4,2,4,2,4,14,
                4,6,6,6,2,6,6,4,2,10,2,6,4,2,4,
                12,2,10,2,6,4,6,2,6,6,4,6,6,12,2,
                6,10,8,4,2,4,2,4,8,10,6,2,4,8,6,
                6,4,2,4,6,2,6,4,8,10,2,10,6,2,4,
                6,2,6,4,2,4,6,6,2,6,6,6,4,6,8,
                4,2,4,2,4,8,6,4,8,10,2,6,6,4,6,
                6,8,4,2,4,2,10,2,12,4,2,4,6,2,10,
                2,4,6,8,6,4,2,6,4,14,4,6,2,4,8,
                6,4,6,2,4,6,2,6,6,10,6,2,6,10,2,
                10,2,10,2,4,2,4,6,2,6,4,2,10,6,8,
                4,2,6,4,6,8,4,2,4,2,12,6,4,6,6,
                6,2,12,4,2,4,8,6,6,4,2,10,2,10,6,
                2,4,6,2,6,4,2,4,6,8,6,4,2,10,6,
                8,6,4,2,4,8,6,4,8,4,6,2,6,12,4,
                6,2,6,4,2,4,2,10,12,2,4,2,10,8,4,
                2,4,6,6,2,10,2,6,18,4,2,4,6,8,6,
                4,6,2,4,6,2,6,6,4,2,4,6,2,10,2,
                4,12,2,12,4,2,4,8,6,4,2,4,6,6,2,
                6,4,2,6,4,6,8,4,2,6,4,14,4,6,2,
                10,2,6,6,4,2,4,6,2,10,2,4,2,22,2,
                4,2,4,6,2,6,4,6,12,2,6,4,2,10,6,
                8,4,2,4,6,8,6,10,2,4,6,2,12,4,2,
                4,6,2,6,4,2,6,12,10,2,4,2,4,6,8,
                4,2,4,12,2,6,4,2,6,4,6,12,6,2,4,
                8,6,4,6,2,4,6,2,6,10,2,4,6,8,4,
                2,4,2,10,2,10,2,4,12,2,6,6,4,6,6,
                2,6,4,2,6,4,6,8,6,6,4,8,10,6,2,
                4,6,8,6,4,2,12,6,4,2,4,2,10,2,10,
                2,4,2,4,8,6,4,2,10,6,2,6,4,8,4,
                6,8,4,2,4,2,4,8,6,4,6,6,6,8,6,
                4,2,4,6,2,6,4,2,4,2,10,2,10,2,10,
                6,2,6,4,2,4,6,6,8,6,6,10,12,2,4,
                2,4,8,10,6,2,4,8,6,6,4,2,4,6,2,
                6,4,6,2,10,2,10,2,6,4,6,2,6,4,6,
                6,6,2,6,6,6,4,6,8,4,2,4,2,4,14,
                4,8,4,6,2,6,6,4,2,10,8,4,2,4,12,
                2,10,2,4,2,4,6,2,12,4,6,8,10,2,6,
                4,6,8,4,6,2,4,8,6,4,6,2,4,6,2,
                6,6,4,6,6,2,6,6,6,10,2,10,6,2,4,
                6,2,6,4,2,10,6,2,6,4,2,6,4,6,8,
                4,2,4,2,12,6,4,6,2,10,2,12,4,6,8,
                6,4,2,4,2,10,2,16,2,4,6,2,10,2,4,
                6,6,2,6,4,2,10,14,6,4,2,4,8,6,4,
                6,2,4,6,2,6,6,6,4,6,2,6,4,6,2,
                10,12,2,4,2,10,2,6,4,2,4,6,6,12,2,
                6,4,14,4,2,4,2,12,6,4,6,6,6,2,6,
                6,4,2,4,6,2,6,6,4,12,2,12,4,2,4,
                6,2,6,4,2,4,6,8,6,4,2,6,4,6,8,
                4,2,4,2,4,14,4,8,10,2,6,10,2,4,6,
                2,10,2,4,2,12,10,2,4,2,4,6,8,4,6,
                6,6,2,6,4,2,6,10,8,4,2,4,6,8,6,
                10,2,4,6,2,6,6,4,2,4,6,2,10,2,6,
                10,2,10,2,4,2,4,14,4,2,4,12,2,6,4,
                2,6,4,6,12,2,6,4,8,6,4,6,2,4,6,
                2,6,10,2,4,6,2,6,4,2,4,2,10,12,2,
                4,6,6,2,6,6,4,12,2,6,4,2,10,6,8,
                4,2,6,4,8,6,10,2,4,6,14,4,2,10,2,
                6,4,2,4,2,12,10,2,4,2,4,8,6,4,2,
                4,6,6,2,6,4,8,4,6,8,4,6,2,4,8,
                6,4,6,6,6,2,6,6,4,2,4,6,8,4,2,
                4,2,10,2,10,2,6,10,2,6,4,2,4,6,6,
                8,4,2,6,10,8,6,4,2,4,8,10,6,2,4,
                8,6,6,4,2,4,8,6,4,6,2,10,2,10,2,
                4,2,4,6,2,6,4,2,10,6,2,6,12,4,6,
                8,4,2,4,2,4,8,6,4,8,4,6,8,6,4,
                2,4,6,8,4,2,4,2,10,2,10,2,4,6,6,
                2,10,2,4,6,8,6,6,6,4,6,12,6,2,4,
                8,6,4,6,2,4,8,6,6,4,6,6,2,6,6,
                4,2,10,2,10,2,6,4,6,2,6,4,12,6,2,
                6,4,2,6,4,6,8,4,2,4,2,18,4,6,2,
                4,6,2,12,4,2,12,6,4,2,4,12,2,10,6,
                2,4,6,2,6,6,4,6,6,2,10,2,10,6,8,
                6,4,2,4,8,6,4,6,2,4,6,2,6,6,6,
                4,6,2,6,4,2,6,10,12,6,2,10,2,6,4,
                2,4,6,6,2,10,2,6,4,14,4,2,4,2,4,
                8,6,4,6,2,10,2,6,6,4,6,6,2,6,4,
                2,4,12,2,12,4,2,4,6,2,10,2,4,6,6,
                2,6,4,2,6,4,14,4,2,4,2,4,14,4,6,
                2,10,2,6,6,6,4,6,2,10,6,2,12,10,2,
                4,2,4,6,2,6,4,6,6,6,8,4,2,6,4,
                6,8,4,2,4,14,6,10,6,6,2,6,6,4,2,
                4,6,2,6,6,6,10,2,10,2,4,2,4,6,8,
                4,2,4,14,6,4,2,6,4,6,12,2,4,2,4,
                8,6,4,8,4,6,2,6,10,2,4,6,2,6,4,
                2,4,2,10,2,10,2,4,6,6,8,6,4,6,6,
                2,6,4,2,6,10,8,4,2,10,8,6,4,6,2,
                4,6,8,6,4,2,10,2,10,2,4,2,10,2,10,
                2,4,2,4,8,6,4,2,4,6,6,2,6,4,8,
                4,6,8,4,2,6,4,8,6,4,6,6,6,2,6,
                6,4,2,4,6,2,6,4,2,4,2,10,12,2,6,
                4,6,2,6,4,2,4,12,8,4,2,16,8,4,2,
                4,2,4,8,16,2,4,8,12,4,2,4,6,2,6,
                4,6,2,12,10,2,4,2,4,6,2,6,4,2,4,
                6,6,2,6,6,6,4,6,8,4,6,2,4,8,6,
                4,8,4,6,2,6,6,4,2,4,6,8,4,2,4,
                2,10,2,10,2,4,2,10,2,10,2,4,6,8,6,
                4,2,6,4,6,8,10,2,4,8,10,6,2,4,6,
                2,6,6,4,6,8,6,6,4,2,10,2,10,2,4,
                2,4,6,2,6,4,2,10,6,2,6,4,8,4,6,
                8,4,2,4,2,12,6,4,6,2,4,6,14,4,2,
                4,8,6,4,2,4,2,10,2,10,6,6,6,2,6,
                4,2,4,6,6,2,6,6,10,6,14,4,2,4,8,
                6,4,6,2,4,8,6,6,6,4,6,2,6,4,2,
                4,2,10,12,2,6,10,2,6,4,6,6,6,2,10,
                2,6,4,14,4,2,4,2,4,14,4,6,2,4,6,
                2,6,6,4,2,10,2,6,4,2,4,12,2,12,4,
                2,4,6,2,6,6,4,6,6,2,10,2,6,4,6,
                8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,
                2,4,6,2,10,2,6,12,10,6,2,4,6,2,6,
                4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,
                6,8,6,10,2,10,2,6,6,4,6,6,2,6,4,
                2,6,10,2,12,4,2,4,6,12,2,4,12,2,6,
                4,2,6,4,18,2,4,2,4,8,6,4,6,2,4,
                6,2,6,12,4,6,2,6,4,6,2,10,2,10,2,
                4,6,6,2,6,6,4,6,6,8,4,2,6,4,6,
                8,4,2,6,12,6,4,6,6,6,8,6,4,2,10,
                2,6,6,4,2,10,2,10,2,4,2,4,8,6,4,
                2,4,6,8,6,4,8,4,6,8,4,2,4,2,4,
                8,6,4,12,6,2,6,10,2,4,6,2,6,4,2,
                4,2,10,2,10,2,6,4,6,8,4,2,4,6,6,
                8,4,2,6,10,8,4,2,4,6,8,10,6,2,4,
                8,6,6,4,2,4,6,2,10,6,2,10,2,10,2,
                4,2,4,8,6,4,2,4,6,6,2,6,6,6,4,
                6,8,4,2,6,4,8,6,4,8,4,6,2,6,6,
                4,2,4,6,8,4,2,4,2,10,12,2,4,2,4,
                6,2,10,2,4,14,6,4,2,10,6,8,4,6,2,
                4,8,6,10,2,4,6,2,12,4,6,6,2,6,6,
                4,2,12,10,2,4,2,4,6,2,6,4,2,10,6,
                2,6,4,2,6,4,6,8,4,6,2,12,6,4,6,
                2,4,6,2,12,4,2,4,14,4,2,4,2,10,2,
                10,6,2,10,2,6,4,2,4,6,6,2,6,4,2,
                10,6,8,6,4,2,4,8,10,6,2,4,6,2,6,
                6,6,4,8,6,4,2,4,2,10,12,2,4,2,10,
                2,6,4,2,10,6,2,10,8,4,14,4,2,4,2,
                4,8,6,4,6,2,4,6,8,6,4,2,4,6,2,
                6,4,2,4,12,2,12,4,6,6,2,6,4,2,4,
                6,6,2,6,6,6,4,6,12,2,4,2,4,14,4,
                6,2,12,6,6,4,2,4,6,2,10,2,4,2,12,
                10,2,6,4,6,2,6,4,6,6,6,2,6,4,2,
                6,4,6,8,4,2,4,6,14,10,2,4,6,2,6,
                6,4,2,10,2,6,4,2,16,2,10,2,4,2,4,
                6,8,6,4,12,2,10,2,6,4,6,12,2,4,2,
                4,8,6,4,6,2,4,6,2,6,10,2,4,6,2,
                6,4,2,6,10,2,10,6,6,6,2,6,6,4,6,
                6,2,6,4,2,6,4,6,8,4,2,6,4,8,6,
                4,6,2,10,8,6,4,12,2,6,4,2,4,2,10,
                2,12,4,2,4,8,10,2,4,6,6,2,6,4,8,
                4,14,4,2,4,2,4,8,6,4,6,6,6,2,6,
                6,6,4,6,2,6,4,6,2,10,2,10,2,6,4,
                6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,
                2,4,2,12,10,6,6,8,6,6,4,2,4,6,2,
                6,10,2,10,2,10,2,4,2,4,6,2,6,4,2,
                4,6,8,6,6,6,4,6,8,4,2,4,2,4,8,
                6,4,8,4,6,2,6,10,2,4,6,8,4,2,4,
                2,10,2,10,2,4,2,4,6,12,2,4,6,8,6,
                4,2,6,10,8,4,6,6,8,6,4,6,2,4,6,
                2,6,6,4,6,6,2,12,4,2,10,2,10,2,4,
                2,4,8,6,4,2,10,6,2,6,4,2,6,4,6,
                8,4,2,6,12,6,4,6,2,4,6,2,12,4,2,
                4,8,6,4,2,4,2,10,12,6,2,4,6,2,6,
                4,2,4,12,2,6,4,2,10,6,8,6,4,2,4,
                8,6,10,2,4,6,2,12,6,4,6,2,6,4,2,
                4,2,22,2,4,2,10,2,6,4,2,4,6,6,2,
                10,2,6,4,14,4,6,2,4,8,6,4,6,2,4,
                6,2,6,6,4,2,4,6,8,4,2,4,12,2,12,
                4,2,10,2,6,4,2,4,6,6,2,6,4,2,6,
                4,6,8,6,4,2,4,18,6,2,10,2,6,6,4,
                2,4,8,10,2,4,2,12,10,2,4,2,4,6,2,
                6,4,12,6,2,6,4,8,4,6,8,4,2,4,6,
                8,6,10,2,4,6,8,6,4,2,4,6,2,6,4,
                2,6,10,2,10,2,4,6,6,8,4,2,4,12,2,
                6,6,6,4,6,12,2,4,2,4,8,6,4,6,2,
                4,8,6,10,2,4,6,2,6,4,2,4,2,10,2,
                10,2,10,6,2,6,10,6,6,2,6,4,2,6,4,
                6,8,4,2,6,4,14,4,6,2,4,6,8,6,4,
                2,10,2,6,4,2,4,12,2,10,2,4,2,4,8,
                6,6,4,6,6,2,10,8,4,6,8,4,2,4,2,
                4,8,6,4,6,6,6,2,6,6,4,2,4,6,2,
                6,4,2,6,10,2,10,8,4,6,2,6,4,2,4,
                6,6,8,4,2,6,10,8,4,2,4,2,4,8,10,
                6,2,12,6,6,4,6,6,2,6,4,6,2,10,2,
                12,4,2,4,6,2,10,2,4,6,6,2,6,6,6,
                4,14,4,2,4,2,4,8,6,4,8,4,6,2,6,
                6,6,4,6,8,4,6,2,10,2,10,2,4,2,4,
                6,2,10,2,4,6,14,4,2,6,4,6,8,4,6,
                2,12,6,4,6,6,6,2,6,6,4,6,6,2,6,
                6,4,2,10,2,10,2,4,2,4,6,2,6,4,2,
                10,8,6,4,2,6,4,6,8,4,2,4,2,12,6,
                4,8,4,6,2,16,2,4,8,6,4,2,4,2,10,
                2,10,6,2,4,6,8,4,2,4,6,6,2,6,4,
                2,16,8,6,4,6,8,6,4,6,2,4,6,2,6,
                6,6,4,6,2,10,2,4,2,10,12,2,4,2,12,
                6,4,2,4,6,6,2,10,2,6,4,14,4,2,6,
                4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,
                2,6,4,2,4,12,14,4,2,4,6,2,6,4,2,
                4,12,2,6,4,2,10,6,8,4,2,4,2,4,14,
                10,2,10,2,12,4,2,4,6,2,10,2,4,2,12,
                10,2,4,2,4,6,2,6,4,6,6,6,2,6,4,
                2,6,4,6,8,4,6,6,8,6,10,2,4,6,2,
                6,6,4,2,4,6,8,4,2,6,10,2,10,2,4,
                2,10,8,4,2,4,12,2,6,4,2,6,4,6,14,
                4,2,4,8,10,6,2,4,6,2,6,10,2,4,8,
                6,4,2,4,2,10,2,10,2,4,6,6,2,6,6,
                10,6,2,6,4,8,4,6,8,4,2,6,4,8,6,
                4,6,2,4,6,8,6,4,2,10,2,6,4,2,4,
                2,10,2,10,2,4,6,8,6,4,2,4,6,6,2,
                6,12,4,6,12,2,4,2,4,8,6,4,6,6,8,
                6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,
                2,6,4,6,2,6,4,6,6,6,8,4,2,6,10,
                8,4,2,4,2,4,18,6,2,4,8,6,6,4,2,
                10,2,6,4,6,12,2,10,2,4,2,4,6,2,6,
                6,4,6,6,2,12,6,4,6,8,4,2,4,2,4,
                8,6,4,8,4,6,2,6,6,4,2,4,6,8,4,
                2,6,10,2,10,6,2,4,6,2,10,2,4,6,8,
                6,4,2,6,4,6,8,4,6,2,4,8,6,4,6,
                2,10,2,6,6,4,6,6,2,6,6,4,2,10,2,
                12,4,2,4,6,2,10,2,10,6,2,6,4,2,6,
                4,14,4,2,4,2,12,6,4,6,2,4,6,2,12,
                6,4,8,6,4,6,2,10,2,10,6,2,4,6,2,
                6,4,2,4,6,6,8,4,2,10,6,8,6,4,2,
                12,6,4,6,6,6,2,6,6,6,4,6,2,6,6,
                4,2,10,12,2,4,2,10,2,6,4,2,4,6,8,
                10,2,6,4,14,4,2,4,2,4,8,6,4,8,4,
                6,2,6,10,2,4,6,2,6,4,2,4,12,2,12,
                4,2,4,6,8,4,2,4,6,6,2,6,4,2,6,
                10,8,4,2,4,6,14,4,6,2,10,2,6,6,4,
                2,4,6,2,10,2,4,2,12,10,2,4,2,4,8,
                6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,
                10,8,6,10,2,4,6,2,6,6,4,2,4,6,2,
                6,4,2,6,10,12,2,4,2,4,6,8,4,2,4,
                12,2,6,4,2,10,6,12,2,4,2,4,8,6,10,
                2,4,6,2,16,2,4,6,2,6,4,2,4,2,12,
                10,2,4,6,6,2,6,6,4,6,6,2,6,4,2,
                6,4,6,8,4,8,4,8,6,4,6,2,4,6,8,
                6,4,2,10,8,4,2,4,2,10,2,10,2,4,2,
                12,6,4,2,4,6,6,2,6,4,8,4,6,8,6,
                4,2,4,8,10,6,6,6,2,6,6,4,2,4,8,
                6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,
                2,10,6,8,4,8,10,8,4,2,4,2,4,8,10,
                6,2,4,14,6,4,2,4,6,2,6,4,6,2,10,
                2,10,2,4,6,6,2,6,4,2,4,6,6,2,6,
                6,6,4,6,12,2,4,2,4,8,6,4,8,4,8,
                6,6,4,2,4,6,8,4,2,4,2,10,2,10,2,
                6,4,6,2,10,6,6,8,6,4,2,6,4,6,8,
                4,6,2,4,14,4,6,2,4,6,2,6,6,4,12,
                2,6,6,4,12,2,10,2,4,2,4,6,2,6,6,
                10,6,2,10,2,6,4,6,8,4,2,4,2,12,6,
                4,6,2,4,6,2,12,4,2,4,8,6,4,2,6,
                10,2,10,6,2,4,6,2,6,4,2,4,6,6,2,
                6,4,2,10,6,8,6,4,2,4,8,6,4,6,2,
                10,2,6,6,10,6,2,6,4,2,4,2,10,14,4,
                2,10,2,10,2,4,6,6,2,10,2,6,4,14,4,
                2,4,2,4,8,6,4,6,2,4,6,2,6,6,6,
                4,6,2,6,4,6,12,2,12,4,2,4,6,2,6,
                4,2,4,6,6,8,4,2,6,4,6,8,4,2,4,
                2,18,4,6,12,2,6,6,4,2,4,6,2,12,4,
                2,12,10,2,4,2,4,6,2,6,4,6,6,8,6,
                4,2,6,4,6,8,4,2,4,6,8,6,12,4,6,
                2,6,10,2,4,6,2,6,4,2,6,10,2,10,2,
                4,2,4,6,8,4,2,4,12,2,6,4,2,6,10,
                12,2,4,6,8,6,4,6,2,4,6,2,6,10,2,
                4,6,2,10,2,4,2,10,2,10,2,4,6,8,6,
                6,4,6,6,2,6,4,2,6,4,6,8,4,2,6,
                4,8,6,4,6,2,4,6,8,6,4,2,10,2,6,
                4,2,4,2,10,12,2,4,2,4,8,6,4,2,4,
                12,2,6,4,12,6,8,4,2,4,2,4,8,6,10,
                6,6,2,12,4,2,4,6,2,6,4,2,4,2,12,
                10,2,6,4,6,2,6,4,2,4,6,6,8,4,2,
                6,10,8,4,6,2,4,8,10,6,2,4,8,6,6,
                4,2,4,6,8,4,6,2,10,2,10,2,4,2,10,
                2,6,4,2,4,6,6,2,6,6,6,4,6,8,6,
                4,2,4,8,10,8,4,6,2,6,6,4,2,4,14,
                4,2,4,2,10,2,10,2,4,2,4,6,2,10,2,
                10,8,6,4,8,4,6,8,4,6,2,4,8,6,4,
                6,2,4,6,8,6,4,6,6,2,6,6,4,2,10,
                2,10,2,4,6,6,2,6,4,2,10,6,2,6,6,
                6,4,6,12,2,4,2,12,6,4,6,2,4,8,12,
                4,2,4,8,6,4,2,4,2,10,2,10,8,4,6,
                2,6,4,6,6,6,2,6,4,2,10,6,8,6,4,
                2,4,14,4,6,2,4,6,2,6,6,6,10,2,6,
                4,2,4,12,12,2,4,2,10,2,6,6,4,6,6,
                2,10,2,6,4,14,4,2,4,2,4,8,6,4,6,
                2,4,6,2,6,6,4,2,4,6,2,6,4,2,16,
                2
                };
           const int p = 2 * 3 * 5 * 7 * 11 * 13;
            const ulong pp = (ulong)p;
            ulong[] grid = new ulong[p];
 
            if (n <= 3248)
            {
                if (n == 1) return 2;
                int nn = (int)n;
                int totalCount = 1;
                bool isPrime = true;
                int i = 0;
                for (i = 3; i < p; i += 2)
                {
                    for (int j = 3; j * j <= i; j += 2)
                    {
                        if ((i % j) == 0)
                        {
                            isPrime = false;
                            break;
                        }
                    }
                    if (isPrime)
                    {
                        totalCount++;
                        if (totalCount >= nn) break;
                    }
                    else
                        isPrime = true;
                }
                return (ulong)i;
            }
            ulong b = 1;
            ulong count = 3248;
            bool not_ended = true;
            ulong current_prime = 2;
            while (not_ended)
            {
                int j = 0;
                int i = 1;
                for (int ind = 0; ind < p; ind++)
                {
                    if (ind != i)
                    {
                        grid[ind] = 0;
                    }
                    else
                    {
                        grid[ind] = b * pp + (ulong)ind;
                        i = i + step[j];
                        j = ++j % 5760;
                    }
                }
                j = 0;
                ulong a = (ulong)(step[j] + 1);
                while (a * a <= (b + 1) * pp - 1)
                {
                    ulong k = (b * pp) / a;
                    while (k * a < b * (ulong)p)
                        k++;
                    while (k * a <= (b + 1) * pp - 1)
                    {
                        //long gg = (long)(k * a - b * pp);
                        //if (gg >= 0)
                        grid[k * a - b * pp] = 0;
                        k++;
                    }
                    j = ++j % 5760;
                    a = a + (ulong)step[j];
                }              
                int u = 1;
                for (int v=0; v<5760; v++)
                {
                   if (grid[u]!=0)
                    {
                        count++;
                        current_prime = grid[u];
                        if (count >= n)
                            break;
                    }
                    u = u + step[v];
                }                
                if (count >= n)
                    not_ended = false;
                else
                    b++;
            }
            return current_prime;
        }
 
 
        static void Main(string[] args)
        {
            //GenerateDivisibilityTable(13, 1);
            System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
            Console.WriteLine("Enter a number: ");
            string input = Console.ReadLine(); //562229227
            ulong long_int = 0;
            ulong.TryParse(input, out long_int);
            timer.Start();
            Console.WriteLine(NthPrime(long_int));
            timer.Stop();
            Console.WriteLine("Elapsed time is: {0}", timer.Elapsed);
            Console.WriteLine("ok");
            Console.ReadLine();
        }
    }
}

CSharp

Categories

Share

Follow


KodFor Privacy Policy