Trying to find the 10001st prime number, c#

Question

I am trying to "Find the 10001st prime number" as part of the Project Euler challenges and i have no idea why my code doesn't work. When I tested my isPrime() function, it succeeded in finding whether a number was prime, but my program returns 10200 as the 10001st prime. Why is this?

Here is My Code:

using System;
using System.Collections.Generic;

namespace Challenge_7
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Solution to Project Euler");
            Console.WriteLine("Challenge 7 - Find the 10001st prime");

            Console.WriteLine("\nProject Start:");

            List<int> primes = new List<int>();

            int number = 1;
            while (primes.Count != 10001)
            {
                if (isPrime(number))
                {
                    primes.Add(number);
                    Console.WriteLine(number);
                }

                number++;
            }

            Console.WriteLine("The 10001st prime is: {0}", primes[10000]);

            Console.ReadLine();
        }

        private static bool isPrime(int n)
        {
            bool prime = true;

            for (int i = 1; i <= Math.Ceiling(Math.Sqrt(n)); i++)
            {
                for (int j = 1; j <= Math.Ceiling(Math.Sqrt(n)); j++)
                {
                    if (i * j == n)
                    {
                        prime = false;
                    }
                }
            }
            return prime;
        }
    }
}

As Peter mentioned in the answer, your approach was not correct. There are a lot of approaches for checking if a number is prime on SOF. I would recommend you to study and try this: https://stackoverflow.com/a/15743238/4329813 — popsiporkkanaa, Jul 21 '18 at 15:57
Your approach with `Math.Sqrt()` should only be applied to one number for the check `i * j == n`, but not for both values. — Progman, Jul 21 '18 at 16:17
`Sqrt(10200) is 100.995` and `10200 = 2 * 5100` but your `for loop` never reach the `5100` to check `2 * 5100`! — Hossein Golshani, Jul 21 '18 at 18:23

score 5 · Answer 1 · answered Jul 21 '18 at 15:48

Here's a hint::

Imagine a number that is the product of 3 primes. Lets say 3, 5, and 7 (or) 105;

sqrt(105) == 10.2 so ceiling is 11

There aren't two numbers less than 11 that multiply to 105. So your algorithm would falsely return true!

Try Again! :-D

score 1 · Accepted Answer · answered Jul 21 '18 at 18:40

The problem is in you loops. Math.Ceiling(Math.Sqrt(10200)) is 101 and you need to check 102 * 100 = 10200 but your loops never reaches 102 and returns 10200 as prime!

You can use the code below for isPrime. It is exists in this link and I changed to C# for you:

private static bool isPrime(int n)
{
    if (n <= 1)
        return false;
    else if (n <= 3)
        return true;
    else if (n % 2 == 0 || n % 3 == 0)
        return false;
    int i = 5;
    while (i * i <= n)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
        i += 6;
    }
    return true;
}

John Kennedy Mendoza Aquino · Answer 3 · 2018-09-17T17:49:21.967

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace nthPrimeNumber
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong starting_number = 1;
            ulong last_number = 200000; //only this value needs adjustment
            ulong nth_primenumber = 0;
            ulong a;
            ulong b;
            ulong c;
            for (a = starting_number; a <= last_number; a++)
            {
                b = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(a)));
                for (c = 2; c <= b; c++)
                {
                    if (a == 1 || (a % c == 0 && c != b))
                    {
                        break;
                    }
                    else
                    {
                        if (c == b)
                        {
                            nth_primenumber = nth_primenumber + 1;
                            break;
                        }
                    }
                }
                if (nth_primenumber == 10001)
                {
                    break;
                }
            }
            Console.WriteLine(nth_primenumber + "st" + "prime number is " + a);
            Console.ReadKey();
        }
    }
}

The program above generates prime numbers between 1 and 200000. The program counts the generated prime numbers and checks if the generated prime numbers are already 10001. The program prints the 10001st prime number. If the program doesn't show 10001st (or shows below 10001) in the console, it is because the value of the last_number is small -- then try to adjust the value of the last_number (make it bigger). In this program, I have already adjusted the value of the last_number and will print the 10001st prime number.

Hi John, it's helpful to include an explanation with your answer, not just code. That way it's easier for people to learn from the answer and understand why that code is an answer to their problem. — Tim, Sep 17 '18 at 17:00

Trying to find the 10001st prime number, c#

3 Answers3