資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究勒讓德猜想：概念、演算法、C++ 實現
勒讓德猜想指出，在兩個連續自然數的平方之間始終存在至少一個素數。
數學上來說，在任意兩個數 n2 和 (n+1)2 之間，始終存在一個素數 p。其中 n 是一個自然數。
猜想指的是一個沒有數學證明的結論。因此，勒讓德猜想只是一個沒有數學證明的陳述。
問題陳述
對於一個數字 n，列印從 1 到 n 的範圍內，n2 到 (n+1)2 之間的素數個數。
示例
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，n2 =1，(n+1)2 = 4。
在這個範圍內的素數是 2 和 3。
對於 i = 2，n2 = 4，(n+1)2 = 9。
在這個範圍內的素數是 5 和 7。
對於 i = 3，n2 = 9，(n+1)2 = 16。
在這個範圍內的素數是 11 和 13。
對於 i = 4，n2 = 16，(n+1)2 = 25。
在這個範圍內的素數是 17、19 和 23。
方法
建立一個變數count來維護素數的個數。
從 i = 1 到 n 開始迴圈。
從 j = i^2 到 j = (i+1)2 開始另一個迴圈。
對於每個 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++ 程式設計實現了它們。
我們使用了兩種方法：蠻力法和埃拉托色尼篩法。
更新於： 2023年3月10日
223 次瀏覽
廣告