找到第 10001 个素数

Question

我看了欧拉项目的以下问题：

通过列出前六个素数：2、3、5、7、11、13，我们可以看出第6个素数是13。第 10001 个质数是多少？

我试着求这个数的平方根，然后找到这个数的平方根以下的所有质数，然后用这个数除以所有的平方根，看看每次是否剩下 0。如果一个数不能被其平方根下的所有质数整除，则它是一个质数。我这样做是为了降低程序必须进行的迭代。这是我现在拥有的，我不确定为什么它不起作用。有人知道我做错了什么吗？

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

Answer 1

几点：

在寻找可能的质因数时，您需要检查所有数字直到平方根包括，所以您的条件j < root不正确。
您不必为每个数字重新计算素数。随时保留列表并向其中添加新素数。
只要找到除数就可以跳出foreach循环

改进代码：

List<long> primeNumbers = new List<long>() { 2 };
for (long i = 3; i < long.MaxValue; i += 2)
{
    if(!primeNumbers.Any(p => (i % p) == 0))
    {
        primeNumbers.Add(i);
        if (primeNumbers.Count == 10001)
        {
            Console.WriteLine(i);
            break;
        }
    }
}

给出 104743 作为第 10001 个素数。

Answer 2

我们可以做的是我们可以使用 SieveOfEratosthenes 来制作一个 bool 数组，其中所有的素数值都设置为 true 之后；

1.As 我们发现任何质数都会使计数增加 1；

2.And 当计数等于 10001 时，我们打印它的值并突破循环。

看看 C++ 代码（我建议你先学习 SieveOfEratosthenes）

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

Answer 3

使用 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

#哪个给出 #10001 104743

找到第 10001 个素数

Find the 10001st prime

c#

primes