We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
class Solution
{
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine());
for (int a0 = 0; a0 < t; a0++)
{
int n = int.Parse(Console.ReadLine());
Console.WriteLine(FindNthPrime(n));
}
}
private static int FindNthPrime(int n)
{
int limit = 200000; // Choose a higher limit to ensure we find the nth prime
bool[] isPrime = SieveOfAtkin(limit);
int count = 0;
for (int i = 2; i < isPrime.Length; i++)
{
if (isPrime[i])
{
count++;
if (count == n)
{
return i;
}
}
}
return -1; // Return -1 if nth prime is not found within the limit
}
private static bool[] SieveOfAtkin(int limit)
{
bool[] isPrime = new bool[limit + 1];
Array.Fill(isPrime, false);
int sqrtLimit = (int)Math.Sqrt(limit) + 1;
for (int x = 1; x < sqrtLimit; x++)
{
for (int y = 1; y < sqrtLimit; y++)
{
int n = (4 * x * x) + (y * y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5))
{
isPrime[n] = !isPrime[n];
}
n = (3 * x * x) + (y * y);
if (n <= limit && n % 12 == 7)
{
isPrime[n] = !isPrime[n];
}
n = (3 * x * x) - (y * y);
if (x > y && n <= limit && n % 12 == 11)
{
isPrime[n] = !isPrime[n];
}
}
}
for (int i = 5; i < sqrtLimit; i++)
{
if (isPrime[i])
{
for (int j = i * i; j <= limit; j += i * i)
{
isPrime[j] = false;
}
}
}
isPrime[2] = isPrime[3] = true; // 2 and 3 are primes
return isPrime;
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #7: 10001st prime
You are viewing a single comment's thread. Return to all comments →
C# code :
using System;
class Solution { static void Main(string[] args) { int t = int.Parse(Console.ReadLine());
}