資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Vantieghems 素數測試定理
問題陳述包括使用 Vantieghems 定理進行素數測試，即我們將檢查使用者輸入的正數 N，並使用 Vantieghems 定理列印該數是否為素數。
Vantieghem 定理
Vantieghems 素數定理指出，如果從 1 到 N−1 的 i 值的 $\mathrm{2^{i}−1}$ 的乘積與模 $\mathrm{2^{N}−1}$ 的 N 同餘，則正數 N 為素數。
如果這兩個值同餘，則數字 N 是素數，否則不是素數。
同餘數：如果兩個給定數字的差被 n 整除，或者可以說 n 是兩個數字差的因子之一，則這兩個數字被稱為模 n 同餘。根據該定理，如果 $\mathrm{2^{N}−1}$ 是 $\mathrm{2^{i}−1}$ 的乘積與 N 的差的因子之一，即它除以差後餘數為 0，則這兩個數字將是同餘數。
讓我們用一些例子來理解這個定理。
輸入
N=3
輸出
Yes
解釋 - 從 1 到 N−1（即 1<=i<=N−1）的 i 值的 $\mathrm{2^{i}−1}$ 的乘積為 $\mathrm{(2^{1}−1)*(2^{2}−1)=1*3=3}$
N 的值為 3，因此為了使這些數字同餘，兩個數字的差（即 0）必須被 $\mathrm{(2^{N}−1)}$ 整除。
由於在這種情況下滿足了 Vantieghems 定理的條件，因此 3 是素數。
輸入
N=5
輸出
Yes
解釋 - $\mathrm{(2^{i}−1)}$ 的乘積，其中 i 在這種情況下從 1 到 4，因為 N=5。
$\mathrm{(2^{1}−1)*(2^{2}−1)*(2^{3}−1)*(2^{4}−1)=1*3*7*15=315}$
這裡 N 的值為 5，因此為了使 315 和 5 模 $\mathrm{(2^{N}−1)}$（即 31）同餘，兩個數字 315 和 5 的差必須被 31 整除且沒有餘數。
差為 310，除以 31 得到 10，因此 5 是素數。
輸入
N=6
輸出
No
解釋 - $\mathrm{(2^{i}−1)}$ 的乘積，其中 1<=i<=N−1。在這種情況下，對於 N=6，i 將從 1 到 5。因此，乘積的值將為：
$\mathrm{(2^{1}−1)*(2^{2}−1)*(2^{3}−1)*(2^{4}−1)*(2^{5}−1)=1*3*7*15*31=9765}$
N 的值為 6。因此，為了使 9765 和 6 模 $\mathrm{(2^{N}−1)\:i.e\:(2^{6}−1)=63}$ 同餘，63 必須是 $\mathrm{(2^{i}−1)}$ 的乘積與 N 的差（即 9765−6=9759）的因子之一。
由於 63 不是 9759 的因子，因此 6 不是素數。
我們將在 C++ 中使用素數的 Vantieghems 定理條件來檢查給定的數字 N 是否為素數。
演算法
因為我們知道任何正數 N 只有在從 1 到 N−1 的 i 值的 $\mathrm{2^{i}−1}$ 的乘積與 N 本身模 $\mathrm{2^{N}−1}$ 同餘時才是素數。
這意味著 $\mathrm{2^{i}−1}$ 的乘積與 N 的差必須是 $\mathrm{2^{N}−1}$ 的倍數，或者換句話說，差必須能被 $\mathrm{2^{N}−1}$ 整除。
為了根據 Vantieghems 定理檢查一個數字是否為素數，我們將簡單地從 i=2 迭代到 i<=N−1，因為對於 i=1，答案將為 1。現在，我們將一直儲存每個 i 值的 $\mathrm{2^{i}−1}$ 的乘積，直到 i=N−1 以獲得乘積的值。
為了計算 $\mathrm{2^{i}−1}$ 的值，我們將使用按位運算子，即用 i 的值左移 1，因為當我們將任何數字 n 左移 i 時，結果等於 $\mathrm{n*2^{i}}$。因此，在這種情況下，我們將 1 左移 i 以獲得 $\mathrm{2^{i}}$ 的值。
一旦我們得到乘積的值，我們將檢查 $\mathrm{2^{i}−1}$ 的乘積與 N 模 $\mathrm{2^{N}−1}$ 是否同餘。為了使 $\mathrm{2^{i}−1}$ 的乘積與 N 同餘，這兩個數的差必須能被 $\mathrm{2^{N}−1}$ 整除，因此我們將檢查差模 $\mathrm{2^{N}−1}$ 是否等於零。如果它等於零，則該數字為素數。
為了計算 $\mathrm{2^{N}−1}$ 的值，我們將簡單地將 1 左移 N，這將等於 $\mathrm{1*2^{N}}$。
我們將在這個演算法中使用 C++ 來檢查數字是否為素數。
方法
在我們的方法中實現 Vantieghem 定理的步驟
為了檢查給定的數字是否為素數，我們將建立一個函式，在其中我們將使用根據 Vantieghem 定理判斷一個數字是否為素數的條件。
然後初始化一個變數來儲存 $\mathrm{2^{i}−1}$ 的乘積，其中 1<=i<=N−1（N 是給定的數字）。該變數應為 long long 資料型別，因為 $\mathrm{2^{i}−1}$ 的乘積可能值很大。
然後，我們將在一個 for 迴圈中從 i=1 迭代到 i<N，並使用左移運算子計算 $\mathrm{2^{i}−1}$ 的乘積來計算 $\mathrm{2^{i}}$ 的值。
一旦我們得到 $\mathrm{2^{i}−1}$ 的乘積，我們現在將檢查 $\mathrm{2^{i}−1}$ 與 N 的差是否能被 $\mathrm{2^{N}−1}$ 整除，因為這兩個數的差必須是 $\mathrm{2^{N}−1}$ 的倍數才能是素數。
如果條件滿足，我們將返回該數字為素數，否則我們將返回該數字不是素數。
示例
// C++ code to check if the number is a prime number or not using Vantieghem's Theorem
#include <bits/stdc++.h>
using namespace std;
//function to check the condition of Vantieghem's Theorem for a number to be a prime
bool check(int N)
{
if(N==1){
return false;
}
long long product = 1; //to store the product of 2^i-1
for (int i=1; i < N; i++) {
//to find the product of 2^i-1, where 1<=i<=N-1
product = product*((1LL << i) - 1);
}
//to check the condition of Vantieghem's Theorem
//the product of 2^i-1 - N should be the multiple of 2^N -1
if ((product-N) % ((1LL << N) - 1) == 0 ){ //using left shift operator to calculate 2^N
return true;
}
else{
return false;
}
}
int main()
{
int N;
N=1;
//calling the function
if(check(N)==true){
cout<<N<<" is a prime number"<<endl;
}
else{
cout<<N<<" is not a prime number"<<endl;
}
return 0;
}
輸出
1 is not a prime number
注意：該程式碼將為 N 從 1 到 11 的值提供正確的輸出，因為對於 N>11，在計算 $\mathrm{2^i−1}$ 的值時，long long 資料型別會發生溢位。
時間複雜度 - O(N)，因為我們在 for 迴圈中迭代 N 次來計算 2^i−1 的乘積。
空間複雜度 - O(1)，因為沒有使用額外的空間來解決問題。
結論
在本文中，我們詳細討論了 Vantieghem 定理，用於檢查數字是否為素數。我們在 C++ 中的程式碼中使用根據 Vantieghem 定理判斷數字是否為素數的條件，以檢查該數字是否為素數。
希望您理解了 Vantieghem 定理，並在閱讀本文後解決了您關於該定理的所有疑問。
82 次瀏覽
