Erathothenes、Jacobi

Erathothenes、Jacobi

实验报告

实验目的

1. 通过编程实现对Erathothenes筛法的熟悉和掌握
2. 通过编程实现对jacobi_symbol计算的熟悉和掌握

实验环境

代码编辑软件：VSCODE
语言：C++、cppStandard: c++17、编译器：mingw64-GCC

Eratosthenes筛法

实验原理

古希腊数学家Eratosthenes(276~194 BC)所提出的一种方法, 给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去。能够生成所有 ≤ N ≤N ≤N的素数表, 直到2004年才被改进。改进版本的核心思想是若 n ≤ N n≤N n≤N且n是合数，则n必有一不大于 N sqrt{N} N ​的素因子。最佳筛法的伪码表根据伪码表示的提示，在实际编码中，既要考虑程序的正确性，又要考虑程序的计算开销和存储开销，我们有以下优化算法的启发：

1. 在筛选素数的过程中，设置一个bool型的数组对计算和存储开销较方便控制，以0、1来记录是否为素数
2. 若i不是素数，可以不剔除其倍数，其倍数已经被其因数剔除
3. 不必从 i ∗ 2 i*2 i∗2开始筛，在 i = 2 i=2 i=2时筛过;也不必在 i ∗ 3 i*3 i∗3时开始…;不必从 i ( i − 1 ) i(i-1) i(i−1)时开始；因为在2、3的时候就已经被筛选过了，就从 i ∗ i i*i i∗i开始

实验过程

1. 将通过C++代码的具体编写实现对Eratosthenes算法的理解
2. 通过设置对比实验，从计算时间上观测时间上最优的Eratosthenes相比于初始Eratosthenes的改进效果
3. 引入vector简化编码

代码

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <ctime>
using namespace std;// 书上的最优化的Eratosthenes算法  
vector<long> sieveofEratosthenes(long n) {clock_t start,end;start = clock();// 确认素数vector<bool> isPrime(n + 1, true); // 初始化所有数均为素数，直接标记2-n，索引从0开始，为n+1  long m = sqrt(n); // 只需要筛选到sqrt(n)即可  for (long i = 2; i <= m; i++) { // 从2开始，将它的倍数都标记为非素数  if (isPrime[i]) { // 首先确认是否是素数，再用素数筛倍数for (long j = i * i; j <= n; j += i) {isPrime[j] = false;}}}end = clock();cout<<"sieve of Eratosthenes timeclock is: "<<double(end-start)<<"ms"<<endl;// 记录素数vector<long> primes;for (long i = 2; i <= n; i++) {if (isPrime[i]) {primes.push_back(i); }}return primes;
}vector<long> easyEratosthenes(long n) {// 确认素数clock_t start,end;start = clock();vector<bool> isPrime(n + 1, true); // 初始化所有数均为素数，直接标记2-n，索引从0开始，为n+1   for (long i = 2; i <= n; i++) { // 从2开始，将它的倍数都标记为非素数  for (long j = i * 2; j <= n; j += i) {isPrime[j] = false;}}end = clock();cout<<"easyEratosthenes timeclock is: "<<double(end-start)<<"ms"<<endl;
}int main() {long n;cout << "input the n:" << endl;cin >> n;vector<long> primes = sieveofEratosthenes(n);easyEratosthenes(n);/*for (long prime : primes) {cout << prime <<" "<< endl;    }return 0;*/
}

实验结果

结果分析，时间上最优的筛法和最原始的筛法，在结果上是完全正确的且一致的，但是在计算速度上差距甚大，在10000000的时候差距接近1：5.5。但是由于代码为了便于编写使用了vector函数，若使用最简单的数组来做，运行速度和存储效率可能还对提升，但这不是这次实验的主要目的。

Jacobi_symbol的计算

引入雅可比符号，正是因为计算勒让德符号时，需要把 n n n分解成标准分解式，这常常时很麻烦的，这也是运用勒让德符号进行计算时的缺点，避开这个缺点，就是引入雅可比符号，它的计算法则，容易由勒让德符号的性质推出。

实验原理

1. 定理一：
   若 n ≡ n 1 ( m o d m ) 和 ( n , m ) = 1 n≡n_1(mod m)和(n,m)=1 n≡n1​(modm)和(n,m)=1，则
   ( n / m ) = ( n 1 / m ) (n/m)=(n_1 /m) (n/m)=(n1​/m)
   若 ( n , m ) = ( n , m 1 ) = 1 (n,m)=(n,m_1)=1 (n,m)=(n,m1​)=1，则
   ( n / m ) ( n / m 1 ) = ( n / m m 1 ) (n/m)(n/m_1)=(n/mm_1) (n/m)(n/m1​)=(n/mm1​)
   若(n,m)=(n_1,m)=1，则
   ( n / m ) = ( n 1 / m ) = ( n n 1 / m ) (n/m)=(n_1/m)=(nn_1/m) (n/m)=(n1​/m)=(nn1​/m)
2. 定理二：
   ( − 1 / m ) = ( − 1 ) ( m − 1 ) / 2 (-1/m)=(-1)^{(m-1)/2} (−1/m)=(−1)(m−1)/2
3. 定理三：
   ( 2 / m ) = ( − 1 ) m 2 − 1 (2/m)=(-1)^{m^2-1} (2/m)=(−1)m2−1
4. 定理四：互反律
   若 m m m与 n n n是第二个正奇数，则 ( n , m ) = 1 (n,m)=1 (n,m)=1，则
   ( m / n ) ( n / m ) = ( − 1 ) ( m − 1 ) ( n − 1 ) / 4 (m/n)(n/m)=(-1)^{(m-1)(n-1)/4} (m/n)(n/m)=(−1)(m−1)(n−1)/4

分析，利用以上定理即可计算雅可比符号，这是柯召《数论讲义》上的定理，上述定理经过某些推导可产生更具体的结论，下面这套：

5. 如果 n n n是一个正奇数，则 m 1 ≡ m 2 ( m o d n ) m_1≡m_2 (mod n) m1​≡m2​(modn)，那么
   ( m 1 / n ) = ( m 2 / n ) (m_1/n)=(m_2/n) (m1​/n)=(m2​/n)
6. 如果 n n n是一个正奇数，那么
   ( 2 / n ) = 1 n ≡ ± 1 ( m o d 8 ) ； ( 2 / n ) = − 1 n ≡ ± 3 ( m o d 8 ) (2/n)=1 n≡±1(mod 8)；(2/n)=-1 n≡±3(mod 8) (2/n)=1n≡±1(mod8)；(2/n)=−1n≡±3(mod8)
7. 如果 n n n是一个正奇数，那么
   ( m 1 m 2 / n ) = ( m 1 / n ) ( m 2 / n ) (m_1m_2/n)=(m_1/n)(m_2/n) (m1​m2​/n)=(m1​/n)(m2​/n)
   特别地，如果 m = 2 k t m=2^kt m=2kt且 t t t为一个奇数，那么
   ( m / n ) = ( 2 / n ) k ( t / n ) (m/n)=(2/n)^k(t/n) (m/n)=(2/n)k(t/n)
8. 如果 m m m和 n n n是正奇数，那么
   ( m / n ) = − ( n / m ) m ≡ n ≡ 3 ( m o d 4 ) ， ( m / n ) = ( n / m ) 其他 (m/n)=-(n/m) m≡n≡3(mod 4)，(m/n)=(n/m) 其他 (m/n)=−(n/m)m≡n≡3(mod4)，(m/n)=(n/m)其他

实验过程

通过C++编写实现对雅可比符号的计算，然后验证雅可比符号计算的正确性，由于上述实验原理本质相同，在算术上的改进效果甚微，因此在本代码的编写中考虑到计算的特征，准备对雅可比符号的计算函数设计嵌套模式。

代码

#include <iostream>  
using namespace std;  int jacobiSymbol(int a, int n) {if (a == 0) {return 0;}if (a == -1){if((n-1)%2) return 1;else return -1;}if (n == 1) {return 1;}if (a % 2 == 0) { //定理三应用int k=(n^2-1)%8;if (k%2 == 0) return jacobiSymbol(a/2,n);else return -jacobiSymbol(a/2, n);}if (a<n && n % 2 == 1 && a % 2 == 1) {int zf = ((a-1)*(n-1))/4;              // 互反正负标识位if (zf%2) return jacobiSymbol(n, a);else return -jacobiSymbol(n,a);}if (a>n) {  a = a % n; return jacobiSymbol(a, n);}
}int main() {  int a, n;  cout << "Enter the value of a: ";  cin >> a;  cout << "Enter the value of n which must be the odd integer: ";  cin >> n;  int result = jacobiSymbol(a, n);  cout << "The Jacobi_symobol is "<<result<<endl;return 0;  
}

实验结果

结果表明，雅可比符号计算具有正确性