skkn cấp tỉnh một số ứng dụng định lý fermat nhỏ trong lập trình

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (365.89 KB, 28 trang )

Trang 1<div class="page_container" data-page="1">

M C L CỤC LỤCỤC LỤC

PHẦN I. MỞ ĐẦU...1

I. Lý do chọn đề tài...1

II. Mục tiêu đề tài...1

1. Đối với giáo viên:...1

2. Đối với học sinh...1

III. Phạm vi nghiên cứu...2

II.1. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố...2

II.2. Ứng dụng định lý FERMAT nhỏ để tính đồng dư...2

IV. Phương pháp nghiên cứu...2

PHẦN II. NỘI DUNG...3

I. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố...3

I.1. Định lý FERMAT nhỏ...3

I.2. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố...3

2.3. Thuật toán Rabin-Miller...6

2.3.1. Ý tưởng...6

2.3.2. Phép thử xác suất (Probabilistic)...7

2.3.3. Thuật tốn đơn định (Deterministic)...8

I.3. Một số ví dụ áp dụng...9

II. Ứng dụng định lý FERMAT nhỏ để tính đồng dư...15

II.1. Một số tính chất của phép tính đồng dư...15

II.2. Khái niệm về nghịch đảo modulo của một số...15

II.3. Ứng dụng định lý FERMAT nhỏ tính đồng dư của một phân thức...16

II.4. Các ví dụ...18

PHẦN III. KẾT LUẬN...24

TÀI LIỆU THAM KHẢO...25

</div>Trang 2<div class="page_container" data-page="2">

PHẦN I. MỞ ĐẦUI. Lý do chọn đề tài.

Số nguyên tố là những số kỳ bí và hyền diệu, từ hàng ngàn năm nay các nhà tốn họcvẫn khơng ngừng nghiên cứu, tìm hiểu về nó. Cho đến nay có rất nhiều thành quả đã thu đượcvà cũng còn nhiều giả thuyết về số nguyên tố còn chưa được chứng minh. Số nguyên tố làtrọng tâm trong lý thuyết số. Một số bài toán lịch sử liên quan đến số nguyên tố vẫn chưa cólời giải. Chúng bao gồm giả thuyết Goldbach, cho rằng mọi số nguyên chẵn lớn hơn 2 có thểđược biểu diễn thành tổng của hai số nguyên tố, và phỏng đốn về số ngun tố sinh đơi, chorằng có vơ số cặp số nguyên tố chỉ có một số chẵn giữa chúng. Những bài tốn như thế đã gópphần thúc đẩy sự phát triển của nhiều nhánh trong lý thuyết số tập trung vào khía cạnh đạisố và giải tích của các số. Số nguyên tố cũng có ứng dụng trong một số lĩnh vực của côngnghệ thông tin, chẳng hạn như mật mã hóa khóa cơng khai…Chính vì tầm quan trọng của sốnguyên tố nên ngay khi bắt đầu học về lập trình, học sinh đã được làm quen với việc giảiquyết các bài toán liên quan đến số nguyên tố. Trong các kỳ thi học sinh giỏi môn Tin học cáccấp từ trung học cơ sở trở lên có nhiều bài tốn liên quan đến số ngun tố.

Qua nhiều năm giảng dạy môn tin học cho học sinh từ Trung Học CS đến THPT, họcsinh chuyên cũng như không chuyên, qua theo dõi cũng như trực tiếp ra đề thi HSG các cấp,tơi nhận thấy có nhiều bài toán liên quan đến số nguyên tố như: Kiểm tra số nguyên tố, liệt kêcác số nguyên tố trên một đoạn, phân tích ra thừa số nguyên tố, thực hiện phép tính đồngdư(chia lấy dư) các phân thức có giá trị rất lớn. Trong khi đó tài liệu nói về những vấn đề nàykhông đầy đủ, phân tán, chủ yếu là ở các trang mạng, vì vậy đơi khi cịn sơ sài gây khó khăncho học sinh cũng như giáo viên. Đa số học sinh mới chỉ biết thuật toán kiểm tra số nguyên tốtương đối nhỏ, liệt kê các số nguyên tố trên một đoạn liên tiếp không vượt q 107. Về phéptính đồng dư của phân thức thì đa số không nắm được, trừ một số học sinh chuyên có thể nắmđược nhưng nhiều khi chỉ nhớ máy móc mà khơng hiểu bản chất.

Tơi làm đề tài này với mong muốn có một tài liệu phục vụ việc giảng dạy của mình,đồng thời những thầy cơ, học sinh nào thấy cần cũng có thể tham khảo. Với khn khổ củamột sáng kiến kinh nghiệm nên khơng có tham vọng nhiều, tơi chỉ chọn trình bày hai vấn đềlà: Kiểm tra, liệt kê các số nguyên tố trong một đoạn với độ lớn các số đến 264 và tính đồng dưphân thức, với độ lớn tử và mẫu rất lớn. Hai vấn đề này có liên quan rất nhiều đến định lýFermat nhỏ nên đề tài có tên là: MỘT SỐ ỨNG DỤNG ĐỊNH LÝ FERMAT NHỎ TRONGLẬP TRÌNH.

Trong đề tài khơng tránh khỏi cịn có những khiếm khuyết, rất mong nhận được sự gópý từ các bạn bè đồng nghiệp.

II. Mục tiêu đề tài.1. Đối với giáo viên:

 Phục vụ thi giáo viên giỏi.

2. Đối với học sinh.

 Giúp học sinh có một thuật tốn hiệu quả để kiểm tra số nguyên tố lớntrong phạm vi biểu diễn số ngun của ngơn ngữ lập trình.

</div>Trang 3<div class="page_container" data-page="3">

 Giúp học sinh có thuật tốn hiệu quả để tính đồng dư ( kết quả của phépchia lấy dư) của các phân thức nguyên (giá trị của phân thức sau khi rút gọn là nguyên)có giá trị lớn vượt quá phạm vi biểu diễn số nguyên của ngôn ngữ lập trình.

III. Phạm vi nghiên cứu.

II.1. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố

2. Khái niệm về nghịch đảo modulo của một số.

4. Các ví dụ.

- Khơng gian: Đề tài được thực hiện tại trường THPT chuyên Lam Sơn.- Thời gian thực hiện: 2023- 2024.

IV. Phương pháp nghiên cứu.

 Kinh nghiệm bản thân, thảo luận, sưu tầm tài liệu, thử nghiệm thực tế,rút kinh nghiệm từ các tiết dạy trên lớp.

khảo của các tác giả và tra cứu trên mạng internet với các đề thi Học sinh Giỏi rút ranhững kinh nghiệm, hệ thống lại kiến thức, mở ra các hướng mới.

sinh giỏi để nắm tình hình trong việc giải các bài toán tin về số.

tuyển HSG, các kỳ tập huấn, ra đề; qua tham khảo ý kiến đồng nghiệp, quý Thầy Côđã giảng dạy đội tuyển nhiều năm, từ đó rút ra được những vấn đề học sinh cịn yếucần được bổ sung, những tài liệu nào giáo viên và học sinh đang cần.

 Phương pháp phân tích lý luận: Phân tích giúp học sinh nắm thật rõ bảnchất vấn đề, lựa chọn được phương pháp giải cho phù hợp.

</div>Trang 4<div class="page_container" data-page="4">

PHẦN II. NỘI DUNG

I. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tốI.1. Định lý FERMAT nhỏ

Định lý: Nếu a là một số nguyên dương và p là một số nguyên tố thì ap≡a(modp).

Giải thích: Dấu ≡ đọc là đồng dư, nội dung định lý khẳng định nếu a là sốnguyên dương, p là nguyên tố thì ap và a khi chia cho p lấy dư (phép % trong ngôn ngữlập trình C++, phép mod trong Pascal..) có cùng một kết quả.

Định lý này cịn có thể viết thu gọn như sau: Nếu a là một số nguyên dương

không chia hết cho p và p là một số nguyên tố thì ap-1 ≡ 1(mod p).

Định lý FERMAT nhỏ là một trường hợp riêng của định lý Euler phát biểu như

sau: Nếu n (n thuộc N*) là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau vớin, thì aφ (n) ≡ 1(mod n). Trong đó φ(n) là ký hiệu của phi hàm Euler đếm số các sốnguyên giữa 1 và n nguyên tố cùng nhau với n.

Định lý Euler là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số nguyêntố thì φ(p) = p − 1.

Việc chứng minh định lý tơi xin khơng trình bày ở đây, nếu bạn đọc muốn tìmhiểu sâu hơn thì xin tra cứu trên mạng, mục đích của đề tài này là ứng dụng định lý.

I.2. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố

2.1.Thực trạng

Việc kiểm tra một số nguyên dương n có phải là số nguyên tố hay không, đa sốhọc sinh thường chỉ mới được trang bị hai giải thuật sau:

a.Giải thuật 1:

Ý tưởng: Nếu n > 1 và n không chia hết cho số nguyên nào

Ta có thể viết một hàm kiểm tra số nguyên n có phải là sốnguyên tố hay không như sau:

boolprimeCheck(long long n){

Độ phức tạp của thuật toán trong trường hợp này là O(

√

n¿. Như vậy trong lậptrình thi đấu hiện nay, khi thời gian chạy thường chỉ cho tối đa là 01 giây thì chỉ có thể

</div>Trang 5<div class="page_container" data-page="5">

áp dụng hàm này với n ≤ 1014. Khi n lớn hơn hoặc khi phải kiểm tra tính ngun tố củanhiều số ngun dương thì thuật tốn trên nhiều khi khơng đáp ứng được. Ta có thể cảitiến thuật toán trên với tư tưởng: Nhận xét nếu số ngun tố n lẻ thì n khơng chia hếtcho một số chẵn bất kì. Do đó nếu n> 2, ta chỉ cần xét các số i lẻ thuộc đoạn [2, √n].

Tương tự, nếu n>3 thì ta chỉ cần xét i là các số không chia hết cho 3. Từ hai nhận xéttrên, nếu n>3 thì ta chỉ cần xét các số i sao cho i chia 6 dư 1 hoặc 5 xem có phải là ướccủa n hay khơng. Thuật tốn cải tiến cụ thể như sau:

boolprimeCheck(int n){

Độ phức tạp của thuật toán này là O(√ n/6¿. Tuy nhiên khin cỡ 1018 hoặc phải kiểm tra nhiều số n thì vẫn khơng đáp ứng được.

b.Giải thuật 2:

Giải thuật này chính là sàng nguyên tố, dùng để đánh dấu các số nguyên tố trong đoạn [1, n]. Ý tưởng như sau: Trước tiên xóa bỏ số 1 ra khỏi tập các số nguyên tố(thường dùng mảng đánh dấu 0 hoặc1), số tiếp theo số 1 là số 2, là số nguyên tố, xóatất cả các bội của 2 ra khỏi bảng. Số đầu tiên khơng bị xóa sau số 2 (số 3) là số nguyêntố, xóa bội của 3,… Thuật toán tiếp tục cho đến khi gặp số nguyên lớn hơn n thì dừng lại. Tất cả các số chưa bị xóa là số nguyên tố.

Ta có thể viết một đánh dấu các số nguyên tố trong đoạn [1, n]như sau:

#define n 10000000bool check[n];void sang(){

memset(check, true, sizeof(check)); check[1] = false;

}}

</div>Trang 6<div class="page_container" data-page="6">

Độ phức tạp của thuật toán này là O(n

√

n¿, tuy nhiên trong thực

văn bản. Mặc dù vậy khi kiểm tra tính nguyên tố của các số lớn hơn

2.2. Ứng dụng định lý FERMAT nhỏ để kiểm tra số nguyên tố

Trong phần này chúng ta sẽ nghiên cứu ứng dụng định lý Fermat nhỏ để kiểmtra số nguyên dương có phải là số nguyên tố hay không.

Định lý Fermat nhỏ khẳng định: Nếu a là một số nguyên dương không chia hết

cho p và p là một số nguyên tố thì ap-1 ≡ 1(mod p).

 Ngược lại, nếu an−1≡1(mod n) thì n có thể là số nguyên tố.

Lưu ý: Ta chỉ chọn a∈[2, n−1] để đảm bảo a không chia hết cho p. Mặt khác

nếu nếu an−1≢1(mod n) thì ta có ngay khẳng định n không phải là nguyên tố, tuy nhiênnếu an−1≡1(mod n) thì vẫn chưa thể khẳng định n là số nguyên tố. Trong trường hợpan−1≡1(mod n), để khẳng định n là nguyên tố hay không ta thử với nhiều giá trị a khácnhau, tuy nhiên cách làm này vẫn chưa hồn tồn chính xác. Ta cũng có thể dùng hàmkiểm tra số nguyên tố primeCheck(long long n) đã trình bày ở phần trên đểkhẳng định n nguyên tố hay không(trong trường hợp phải kiểm tra nhiều giá trị n), tuynhiên cách này chỉ áp dụng khi số lượng số cần kiểm tra không quá nhiều và độ lớncủa các số khơng q lớn.

b.Thuật tốn

Trước hết xây dựng hàm tính ak % n:

Long longluythua(longlong a, long long k, long long

k /= 2; }

return res;}

</div>Trang 7<div class="page_container" data-page="7">

Hàm này có độ phức tạp là O(log k), trong tài liệu giáo khoa chun tin quyển 1đã có trình bày bằng đệ quy, ở đây ta khử đệ quy. Trong hàm này có phép tốn a= a*a%n nên chú ý chỉ chọn a≤109 để không tràn số.

Bây giờ ta cài đặt hàm kiểm tra số n có là số nguyên tố hay không bằng phépthử Fermat:

boolisPrimefermat(long long n){

if (n < 7)

return n == 2 || n == 3 || n == 5;

const int repeatNum = 5;

for (int i = 0; i < repeatNum; ++i)

{

int a = rand() % (n - 3) + 2;

if (luythua(a, n - 1, n) != 1)

return false; }

return true;}

Như đã nói ở trên, phép thử Fermat này khơng hồn tồn chính xác, có nhữngsố n có tính chất với mọi số nguyên a mà gcd(a,n)=1 thì an-1 % n vẫn bằng 1 nhưng sốđó lại khơng phải số nguyên tố, ví dụ n= 561 = 3.11.17 là số có tính chất như trên.Những số có tính chất như 561 người ta gọi là số Carmichael.

Các số Carmichael phân bố rất ít trong tập các số tự nhiên. Theo OEIS-A055553: Số các số Carmichael nhỏ hơn 106 là 43 số.

 Số các số Carmichael nhỏ hơn 109 là 646 số Số các số Carmichael nhỏ hơn 1018 là 1401644 số.

Do đó, các bạn có thể yên tâm khi sử dụng phép thử Fermat nếu test được sinh ngẫunhiên, vì xác suất gặp số Carmichael rất thấp. Nếu test cố tình chọn số Carmichaelhoặc phải kiểm tra các số nguyên tố trên một đoạn liên tiếp các số thì phép thử khơngcịn đáng tin cậy. Rất may là có những phép thử hiệu quả và chính xác hơn phép thửFermat. Trong phần tiếp theo chúng ta sẽ cùng tìm hiểu thuật toán Rabin-Miller.

2.3. Thuật toán Rabin-Miller2.3.1. Ý tưởng

Thuật toán Rabin-Miller là phiên bản mở rộng và mạnh hơn của phép thửFermat. Thuật toán dựa vào nhận xét sau: Với mọi số nguyên dương x, tồn tại duy nhấthai số tự nhiên k,m sao cho x=2k×m và m lẻ.

Ví dụ: 6=21×3, 100=22×25, 9=20×9, 6=21×3,…

</div>Trang 8<div class="page_container" data-page="8">

Do đó, xét số n, ta có thể phân tích n−1 thành 2k×m, với m là số lẻ.

Theo định lý nhỏ Fermat, nếu n là số nguyên tố thì với mọi a sao cho gcd(a,n)=1 ta có: an−1≡1(mod n) ⇔ a^(2k.m) −1≡ 0 (mod n). Vế trái có dạng A2 – B2, khai triểnvế trái ta được đẳng thức tương đương:

[a^(2k−1 .m)+1].[a^(2k−2.m)+1]…(am+1)(am−1)≡0 (mod n)

Vì n là số nguyên tố nên tồn tại ít nhất một trong các nhân tử của vế trái chiahết cho n. Do đó, thay vì kiểm tra kết luận của định lý Fermat nhỏ, ta sẽ kiểm tra điềukiện sau:

 am≡1(mod n) hoặc

 Tồn tại 0≤L≤k−1 sao cho a^(2L.m)≡−1(modn)

Nếu cả hai điều kiện không được thỏa mãn thì chắc chắn n là hợp số.

Nhưng nếu một trong hai điều kiện được thỏa mãn thì n có phải số ngun tốkhơng?

Câu trả lời là khơng. Ví dụ: với n=28, a=19 thì n−1=20×27 và 1927≡−1(mod 28)nhưng n= 28 khơng phải nguyên tố.

Do đó, để áp dụng ý tưởng trên, ta có thể triển khai theo hai cách sau:

2.3.2. Phép thử xác suất (Probabilistic)

Để tăng tính chính xác của thuật tốn ta có thể lặp lại bước kiểm tra với nhiềucơ số a, giống như phép thử Fermat. Hơn thế nữa, chứng minh được nếu n là hợp số,chỉ có ≈25% số cơ số a trong đoạn [2,n−1] thỏa mãn một trong hai điều kiện. Nghĩa làvới hợp số n bất kì, xác suất để thuật tốn chứng minh được n là hợp số sau lần kiểmtra đầu tiên là ≥75%, lần thứ hai là ≥93.75%, lần thứ ba là ≥98.43%, lần thứ x là (1−1/¿x))×100%. Có thể thấy độ chính xác của thuật tốn Rabin-Miller cao hơn nhiều sovới phép thử Fermat, và tất nhiên là đủ tốt cho các bài tốn lập trình thi đấu.

Cài đặt thuật tốn:

k /= 2; }

return res;

}

</div>Trang 9<div class="page_container" data-page="9">

// Kiể m tra điể u kiện thuật toán với a cố định

booltest(longlong a, longlong n, longlong k, longlong m)

return false;}

boolRabinMiller(longlong n){

m /= 2;

k++;

}

const int repeatTime = 3;

for (int i = 0; i < repeatTime; ++i)

{

longlong a = rand() % (n - 3) + 2;

if (!test(a, n, k, m)) return false;

}

return true;}

Độ phức tạp là O(clogn) với c là số giá trị cơ số a ta thử, trong chương trình này cchính là repeatTime = 3.

</div>Trang 10<div class="page_container" data-page="10">

2.3.3. Thuật toán đơn định (Deterministic)

Phép thử xác suất có thể trở thành thuật tốn (đúng 100%) bằng cách thay vìxét a ngẫu nhiên, ta sẽ xét tất cả a bị chặn bởi một hàm theo n. Bach chứng minh đượcchỉ cần xét a∈[2,2ln2n].

Với n đủ lớn thì vẫn có rất nhiều giá trị cần kiểm tra. Hiện nay người ta cũng đãchứng minh được rằng:

for (auto a : checkSet)

if (a!=n &&!test(a, n, k, m)) // a!=n để, tránh trường hợp n =a

return false; //thuộc tập {11,13,17,19,23,29,31,37} //khi đó gcd(a,n)≠ 1 khơng tho,a đk phép thư,,khi đó n coi là hợp sơD

return true;}

I.3. Một số ví dụ áp dụng

Trong phần này chúng ta sẽ xét một số ví dụ cụ thể để hiểu rõ hơn về kỹ thuậtcài đặt và cũng như trong mỗi trường hợp cụ thể thì nên dùng thuật tốn nào.

3.1.Ví dụ 1

</div>Trang 11<div class="page_container" data-page="11">

3.1.1.Bài toán: Cho số nguyên dương n ≤ 4.106, hãy liệt kê các số nguyên tốtrong đoạn từ 1 đến n.

INPUT: Cho trong file NGUYENTO1.INP gồm duy nhất một số nguyên dươngn.

OUTPUT: Ghi ra file NGUYENTO1.OUT các số tìm được trên một dịng theothứ tự tăng dần.

3.1.2.Phân tích: Do đoạn cần liệt kê các số nguyên tố có khoảng cách lớn, các

số trong đoạn này lại khơng q lớn, vì vậy ta sử dụng sàng nguyên tố là tốt hơn cả.

3.1.3.Chương trình

#include <bits/stdc++.h>#define ll long long#define nmax 10000000using namespace std;int n, d=0;

bool check[nmax];void sang()

}}

bool primeCheck(int n){

if (n == 2 || n == 3) return true;

if (n < 3 || n % 2 == 0 || n % 3 == 0) return false;

for (int i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;

return true;}

int main()

</div>Trang 12<div class="page_container" data-page="12">

{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

freopen("NGUYENTO1.INP", "r", stdin); freopen("NGUYENTO1.OUT", "w", stdout); cin>>n;

sang();

for(int i=1; i<= n; i++) if(check[i]) { d++;

cout<<i<<endl; }

cout<<endl<<d; return 0;

Qua thực nghiệm tôi nhận thấy thuật này chạy nhanh hơn khoảng 20 lần khidùng thuật tốn đơn định.

3.2.Ví dụ 2

3.2.1.Bài toán: Cho 2 số nguyên dương L ≤ R≤ 109, R-L≤ 5.103

, hãy liệt kêcác số nguyên tố trong đoạn từ L đến R.

INPUT: Cho trong file NGUYENTO2.INP gồm 2 số nguyên dương L, R.

OUTPUT: Ghi ra file NGUYENTO2.OUT các số tìm được trên một dịng theothứ tự tăng dần.

3.2.2.Phân tích: Việc dùng sàng ngun tố khơng cịn khả thi do R có thể có

giá trị đến 109, do đó ta sẽ áp dụng thuật tốn đơn định với phép thử MillerRabin

để giải quyết bài tốn này.

3.2.3.Chương trình

#include <bits/stdc++.h>#define ll long longusing namespace std;

vector<int> checkSet ={2,3,5,7}; ll L,R, d=0;

long long luythua(long long a, long long k, long longn)

</div>Trang 13<div class="page_container" data-page="13">

a = (a * a) % n; k /= 2;

}

return res;}

bool test(long long a, long long n, long long k, longlong m)

{ long long mod = luythua(a, m, n); if (mod == 1 || mod == n - 1) return true;

for (int l = 1; l < k; ++l) {

mod = (mod * mod) % n; if (mod == n - 1)

return true; }

return false;}

bool MillerRabin(long long n){

if (n == 2 || n == 3 || n == 5 || n == 7) return true;

if (n < 11)

return false;

long long k = 0, m = n - 1; while (m % 2 == 0)

{

m /= 2; k++; }

for (auto a : checkSet)

if (a!=n &&!test(a, n, k, m)) return false;

return true;}

int main(){

</div>Trang 14<div class="page_container" data-page="14">

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

freopen("rabin.INP", "r", stdin); freopen("rabin.OUT", "w", stdout); cin>>L>>R;

if (L<= 2)

{ cout<<2<<" "; L=3;

d++; }

for (ll i=L; i<=R; i++)

if((i&1)&&MillerRabin(i)) { d++;

cout<<i<<" "; }

//cout<<endl<<d;}

Trong chương trình này ta thấy:

vector<int> checkSet ={2,3,5,7}, lý do là L ≤ R≤ 109, như đã trình bày ở trên, tachỉ cần thử 4 giá trị của a là đủ.

3.3.Ví dụ 3

3.3.1.Bài tốn: Cho 2 số nguyên dương L ≤ R≤ 1018, R-L≤ 5.103

, hãy liệt kêcác số nguyên tố trong đoạn từ L đến R.

INPUT: Cho trong file NGUYENTO3.INP gồm 2 số nguyên dương L, R.

OUTPUT: Ghi ra file NGUYENTO3.OUT các số tìm được trên một dịng theothứ tự tăng dần.

3.3.2.Phân tích: Việc dùng sàng ngun tố khơng cịn khả thi do R có thể có

giá trị đến 1018, do đó ta vẫn sẽ áp dụng thuật toán đơn định với phép thửMillerRabin để giải quyết bài tốn này. Tuy nhiên có một số vấn đề phải chỉnhsửa so với ví dụ 2 là:

 vector<int> checkSet ={2,3,5,7,11,13,17,19,23,29,31,37}.

 Hàm luythua phải chỉnh sửa lại vì trong hàm này có phép tốn a = (a * a)% n, Như vậy trong quá trình lặp a có thể gần bằng 1018, khi đó lúc thực hiện phépnhân sẽ bị tràn số.

3.3.3.Chương trình

#include <bits/stdc++.h>#define ll long longusing namespace std;

={2,3,5,7,11,13,17,19,23,29,31,37};ll L,R, d=0;

</div>