本文主要是介绍Erathothenes、Jacobi_Symbol计算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
实验报告
实验目的
- 通过编程实现对Erathothenes筛法的熟悉和掌握
- 通过编程实现对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的素因子。最佳筛法的伪码表根据伪码表示的提示,在实际编码中,既要考虑程序的正确性,又要考虑程序的计算开销和存储开销,我们有以下优化算法的启发:
- 在筛选素数的过程中,设置一个bool型的数组对计算和存储开销较方便控制,以0、1来记录是否为素数
- 若i不是素数,可以不剔除其倍数,其倍数已经被其因数剔除
- 不必从 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开始
实验过程
- 将通过C++代码的具体编写实现对Eratosthenes算法的理解
- 通过设置对比实验,从计算时间上观测时间上最优的Eratosthenes相比于初始Eratosthenes的改进效果
- 引入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分解成标准分解式,这常常时很麻烦的,这也是运用勒让德符号进行计算时的缺点,避开这个缺点,就是引入雅可比符号,它的计算法则,容易由勒让德符号的性质推出。
实验原理
- 定理一:
若 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) - 定理二:
( − 1 / m ) = ( − 1 ) ( m − 1 ) / 2 (-1/m)=(-1)^{(m-1)/2} (−1/m)=(−1)(m−1)/2 - 定理三:
( 2 / m ) = ( − 1 ) m 2 − 1 (2/m)=(-1)^{m^2-1} (2/m)=(−1)m2−1 - 定理四:互反律
若 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
分析,利用以上定理即可计算雅可比符号,这是柯召《数论讲义》上的定理,上述定理经过某些推导可产生更具体的结论,下面这套:
- 如果 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) - 如果 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) - 如果 n n n是一个正奇数,那么
( m 1 m 2 / n ) = ( m 1 / n ) ( m 2 / n ) (m_1m_2/n)=(m_1/n)(m_2/n) (m1m2/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) - 如果 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;
}
实验结果
结果表明,雅可比符号计算具有正确性
这篇关于Erathothenes、Jacobi_Symbol计算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!