数据结构
网络
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 次浏览
