试图找到第 10001 个质数，c#

Question

我正在尝试 "Find the 10001st prime number" 作为 Project Euler 挑战的一部分，但我不知道为什么我的代码不起作用。当我测试我的 isPrime() 函数时，它成功地找到了一个数字是否是素数，但是我的程序 returns 10200 是第 10001 个素数。这是为什么？

这是我的代码：

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;
        }
    }
}

Answer 1

这里有一个提示::

想象一个数是 3 个素数的乘积。比方说 3、5 和 7（或）105；

sqrt(105) == 10.2 所以上限是 11

没有两个小于 11 的数乘以 105。所以你的算法会错误地 return true!

再试一次！ :-D

Answer 2

问题出在你的循环中。 Math.Ceiling(Math.Sqrt(10200)) 是 101 并且您需要检查 102 * 100 = 10200 但您的循环永远不会达到 102 和 returns 10200 作为素数！

您可以使用下面的代码 isPrime。它存在于 this link 中，我为您更改为 C#：

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;
}

Answer 3

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();
        }
    }
}

上面的程序生成了 1 到 200000 之间的素数。程序对生成的素数进行计数，并检查生成的素数是否已经是 10001。程序打印第 10001 个素数。如果程序在控制台中没有显示10001st（或显示在10001以下），那是因为last_number的值太小了——然后尝试调整last_number的值（使其大）。在这个程序中，我已经调整了last_number的值，将打印第10001个素数。

试图找到第 10001 个质数，c#

Trying to find the 10001st prime number, c#

c#

primes