Vantieghems定理用于素数测试

问题陈述包括使用Vantieghems定理进行素数测试，即我们将检查一个正数N，该数将由用户输入，并且通过使用Vantieghems定理打印出该数字是否为素数。

Vantieghem的定理

Vantieghems素数定理指出，一个正数N是一个素数，如果当i的值从1到N−1时的 $\mathrm{2^{i}−1}$ 的乘积与N模 $\mathrm{2^{N}−1}$ 同余。

如果两个值同余，则数字N是一个素数，否则它不是一个素数。

同余数： 如果两个给定数字的差恰好被n整除，或者可以说n是两个数字的差的一个因子，则称这两个数字在模n下是同余的。

根据定理，如果 $\mathrm{2^{N}−1}$ 是 $\mathrm{2^{i}−1}$ 的乘积差的一个因子，即它将差数完全除尽，则这两个数字将是同余的。

让我们用一些例子理解这个定理。

输入：

N=3

输出

Yes

解释 −

当 i 的范围是1到N−1时，即 $1<=i<=N-1$ ，将 i 代入 $\mathrm{2^{i}−1}$ 的乘积，也就是 $\mathrm{(2^{1}−1)*(2^{2}−1)=1*3=3}$

当 N 的值为3时，要使这些数字成为同余数，两个数字的差值必须被 $\mathrm{(2^{N}−1)}$ 整除。

由于在这种情况下满足 Vantieghems 定理的条件，3 是一个质数。

输入

N=5

输出

Yes

解释 − 在这个例子中，i的取值范围是1到4，因为N=5，所以 $\mathrm{(2^{i}−1)}$ 的乘积是。

$\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，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) \mod 163=63}$ 同余，63应该是 $\mathrm{\ (2^{i}−1)}$ 和N的差值9759的因子之一。

由于63不是9759的因子，因此6不是一个质数。

我们将使用Vantieghems定理的条件来检查给定的数N是否为质数，在C++中实现。

算法

因为我们知道任何正数N只有在 $\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}$ 的值时，我们将使用位运算符，即左移1位根据i值，因为当我们将任意数字n左移i位时，结果等于 $\mathrm{n*2^{i}}$ 。因此，在这种情况下，我们将左移1位，得到 $\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位，得到 $\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
一旦我们获得了 $\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;
}