Nth prime number in CSharp
By Jean-Claude Colette 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.
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.
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();
}
}
}
