'Find the 10001st prime

I took a look at the following question from project euler:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

I tried to take the square root of the number and than find all the prime numbers below the square root of the number and then divide the number by all the square roots and see if there is 0 left each time. If the number is not divisible by all the primes under its square root its a prime number. I did this to lower the itterations the programm has to make. Here is what I have now, I am not sure why it isn't working. Anybody knows what i did wrong?

  List<int> primeNumbers = new List<int>();
        bool prime = true;
        bool MainPrime = true;
        int check = 1;
        for (long i = 3; i < long.MaxValue; i++)
        {
            if ((i % 2) != 0)
            {
                int root = Convert.ToInt32(Math.Sqrt(i));
                for (int j = 1; j < root; j++)
                {
                    for (int k = 2; k < j; k++)
                    {
                        if ((j% k) == 0)
                        {
                            prime = false;
                        }
                    }
                    if (prime)
                    {
                        primeNumbers.Add(j);
                    }
                    prime = true;
                }

            }
            foreach (var item in primeNumbers)
            {
                if ((i%item) == 0)
                {
                    MainPrime = false;
                }
            }
            primeNumbers.Clear();
            if (MainPrime)
            {
                check++;
            }
            if (check == 10001)
            {
                Console.WriteLine(i);
                break;

            }
        }

        Console.ReadKey();
c++sharpprimes


Solution 1:[1]

What we can do is we can use SieveOfEratosthenes to make an bool array in which all the prime numbers value are set to be true than after that;

1.As we found any prime number increment the count with 1;

2.And as count get equal to 10001 we print its value and break through the loop.

Have a Look at code in C++ (I recommend you to learn SieveOfEratosthenes first)

#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(long long unsigned n)
{
    bool prime[n];
    memset(prime, true, sizeof(prime));                //This is SieveOfEratosthenes
 
    for (long long  p = 2; p * p <= n; p++)
    {
        if (prime[p] == true) 
        {
            for (long long  i = p * p; i <= n; i += p)      
                prime[i] = false;                         
        }
    }
    
    
    long long count=0;                      //initializing count as 0;
    for (long long  p = 2; p <= n; p++)       //running the loop form 2 to n
       {
         if (prime[p])                      //we have bool array in which all prime number set to true using sieve
           count++;                         //increment the count because we found a prime number 
           if(count==10001)                 // and as count reaches to 10001 we found our number 
           {
           cout<<p;break;}                 // print the answer and also break form the loop
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long unsigned n=999999;
    SieveOfEratosthenes(n);     //pass the value of n in sieve function
    return 0;
}

Solution 2:[2]

Try this one out using python

sp=2
cnt = 1
while cnt <= 10001:
    primeflag = 0
    for j in range(2,sp):
        if(sp%j == 0):
            primeflag = 1
            break;
    if(primeflag == 1):
        pass
    else:
        print(cnt ,sp)
        cnt = cnt +1
    sp =sp+1

#which Gives #10001 104743

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Karmesh Duggar
Solution 2

Related Questions