勒让德猜想：概念、算法、C++ 实现

---

勒让德猜想指出，在两个连续自然数的平方之间始终存在至少一个素数。

数学上来说，在任意两个数 n² 和 (n+1)² 之间，始终存在一个素数 p。其中 n 是一个自然数。

猜想指的是一个没有数学证明的结论。因此，勒让德猜想只是一个没有数学证明的陈述。

问题陈述

对于一个数字 n，打印从 1 到 n 的范围内，n² 到 (n+1)² 之间的素数个数。

示例

Input: 4
Output: 
For i = 1: Total primes in the range 1 and 4 = 2
For i = 2: Total primes in the range 4 and 9 = 2
For i = 3: Total primes in the range 9 and 16 = 2
For i = 4: Total primes in the range 16 and 25 = 3

解释

对于 i =1，n² =1，(n+1)² = 4。

在这个范围内的素数是 2 和 3。

对于 i = 2，n² = 4，(n+1)² = 9。

在这个范围内的素数是 5 和 7。

对于 i = 3，n² = 9，(n+1)² = 16。

在这个范围内的素数是 11 和 13。

对于 i = 4，n² = 16，(n+1)² = 25。

在这个范围内的素数是 17、19 和 23。

方法

• 创建一个变量count来维护素数的个数。

• 从 i = 1 到 n 开始循环。

• 从 j = i^2 到 j = (i+1)² 开始另一个循环。

• 对于每个 j，通过将其除以从 2 到 j 的平方根的数字来检查它是否为素数。

• 如果 j 是素数，则增加 count 的值。

• 为每个 i 打印 count。

示例

下面是一个 C++ 程序，用于查找两个连续自然数的平方之间的素数个数。

#include <bits/stdc++.h>
using namespace std;
//This function checks if a number is prime or not
bool prime(int n){
   if(n==1){
      return false;
   }
   //Check for the factors of n.
   for (int i = 2; i * i <= n; i++)
      if (n % i == 0)
         return false;
      //If no factor other than 1, and the number, then return true.
      return true;
}

//This function prints the number of primes
void legendre_conjecture(int n){
   //count of prime numbers for each number from 1 to n.
   int count;
   
   for(int i=1;i<=n;i++){
      count=0;  
      //Check from i^2 to (i+1)^2.
      for(int j=i*i;j<=((i+1)*(i+1));j++){
         //If prime, increase the count.
         if(prime(j)){
            count++;
         }
      }
      //Print the number of prime numbers from i^2 to (i+1)^2
      cout<<"For i: "<<i<<" "<<"Total primes in the range"<<" "<<(i*i)<<" "<<"and"<<" "<<(i+1)*(i+1)<<" "<<"="<<" "<<count<<endl;
   }
}
int main(void){
   int n = 5;
   cout<<"Value of n: 5"<<endl;
   //Function call.
   legendre_conjecture(n);
   return 0;
}

输出

Value of n: 5
For i: 1 Total primes in the range 1 and 4 = 2
For i: 2 Total primes in the range 4 and 9 = 2
For i: 3 Total primes in the range 9 and 16 = 2
For i: 4 Total primes in the range 16 and 25 = 3
For i: 5 Total primes in the range 25 and 36 = 2

上面的程序适用于较小的输入，但对于较大的输入效率低下。

因此，为了优化它，我们将使用埃拉托色尼筛法。

埃拉托色尼筛法通过筛选不需要的输出找到素数。

示例：（使用埃拉托色尼筛法的优化方法）

下面是一个 C++ 程序，用于使用埃拉托色尼筛法查找 n^2 和 (n+1)^2 之间的素数。

#include <bits/stdc++.h>
using namespace std;
#define size 10001

//This function uses the sieve of the Eratosthenes technique
//to sieve the non primes and then stores the count of
//number of primes from 0 to i in count[i].
void find_primes(vector<int>&count){
   
   //vector to sieve out the non primes
   //initially mark every number as prime
   vector<bool>sieve(size, true);
   for (int i = 2; i * i < size; i++) {
   
      if (sieve[i] == true) {
         //Mark all the multiples as false.
         for (int j = i * 2; j < size; j += i)
         sieve[j] = false;
      }
   }
   //count[i] stores the number of primes from 0 to i.
   count[0] = 0;
   count[1] = 0;
   for (int i = 2; i < size; i++) {
      count[i] = count[i - 1];
      if (sieve[i])
      count[i]++;
   }
}

//This function finds total primes in the given range
int count_primes(int s, int e, vector<int>count){
   return count[e] - count[s - 1];
}
int main(void){

   //count vector will store the count of primes
   vector<int> count(size);
   
   //Function call to sieve out all the nonprimes
   // and store the number of primes in the count vector
   find_primes(count);
   int n = 5;
   cout<<"Value of n:  5"<<endl;
   int start, end;
   for(int i=1;i<=n;i++){
      start=i*i;
      end=(i+1)*(i+1);
      cout<<"For i: "<<i<<" "<<"Total primes in the range"<<" "<<start<<" "<<"and"<<" "<<end<<" "<<"="<<" "<<count_primes(start,end,count)<<endl;
   }
   return 0;
}

输出

Value of n:  5
For i: 1 Total primes in the range 1 and 4 = 2
For i: 2 Total primes in the range 4 and 9 = 2
For i: 3 Total primes in the range 9 and 16 = 2
For i: 4 Total primes in the range 16 and 25 = 3
For i: 5 Total primes in the range 25 and 36 = 2

在本文中，我们了解了勒让德猜想的概念。

我们查看了一些示例，并使用 C++ 编程实现了它们。

我们使用了两种方法：蛮力法和埃拉托色尼筛法。