SKKN Áp dụng phương pháp sàng Eratosthene vào giải các bài toán về số nguyên tố trong ngôn ngữ lập trình C++

n với màu xanh của rừng già làm cho
phong cảnh nơi đây vừa hùng vĩ vừa thơ mộng.
Tại đây, các nhà khảo cổ học đã phát hiện ra một số kho báu bí mậtcủa được các vua Hùng xây dựng rất kiên cố và không thể phá bỏ. Họ cho rằng trong đó có thể là những khối tài sản về lịch sử và văn hóa rất có giá trị và họ tìm cách mở cánh cửa của những kho báu đó.
Trên cửa mỗi kho báu có một bảng gồm 2 hàng, hàng 1 đã ghi sẵn số nguyên dương N (≤106), hàng 2 chứa 2 khoá số K1 và K2 như hình bên.
Trong khi khảo sát, các nhà khảo cổ đã phát hiện một phiến đá có ghi cách để mở khoá như sau: cửa có bảng chứa số N sẽ tương ứng với K1 và K2 là:
N
K1
K2

Điều chỉnh khoá số K1 về số bằng số lượng ước nguyên tố của N;
Điều chỉnh khoá số K2 về số bằng tổng các ước nguyên tố của N thì cánh cửa sẽ tự động mở ra và nhà khảo cổ có thể vào bên trong kho báu một cách dễ dàng.
Ví dụ: Ở nhà kho trên cửa ghi số N=12, có các ước của N là 1, 2, 3, 4, 6, 12 chỉ có 2 ước nguyên tố là 2 và 3 nên K1=2 và K2=5.
Dữ liệu: vào từ filevăn bản PASS.INPchứa duy nhất một số nguyên dương
N;
Kết quả: Ghi ra filevăn bản PASS.OUT hai số nguyên K1 và K2.
Ví dụ:
PASS.INP
PASS.OUT
12
2 5

Ràng buộc:
Có 30% số các test ứng với 30% số điểm của bài có 𝑁 ≤ 1000;
Có 40% số test khác ứng với 40% số điểm của bài có 𝑁 ≤ 104;
Có 30% số test còn lại ứng với 30% số điểm của bài có 𝑁 ≤ 106.
Ý tưởng: Dùng phương pháp sàng ngyên tố
+ Sàng các số nguyên tố nhỏ hơn hoặc bằng N. Đếm số lượng số nguyên tố và tính tổng các số nguyên tố đó.
Chương trình cụ thể như sau:
#include using namespace std; void sang()
{ifstream inp{"PASS.INP"}; ofstream out{"PASS.OUT"}; int n; inp >>n;
bool f[n+1]={0}; int t=0, d=0; f[0]=1; f[1]=1;
for(int i=2; i<=n;i++)
{ if((!f[i]) and (n%i==0) )
{ d++; t+=i;
for(int j=2; i*j<=n;j++) f[i*j]=1;
}
}
out<<d<<" "<< t << '\n'; return;
}
int main()
{
sang(); return 0;
}
Bài toán 4:	Tìm số Fibonacci nguyên tố
Dãy số Fibonacci là dãy được xác định như sau: f0=0, f1=1 và fn= fn-1+ fn-2 với n=2,3.
Em hãy tìm số Fibonacci lớn nhất là số nguyên tố và nhỏ hơn số M cho trước.
Dữ liệu vào: Từ file văn bản Fibonacci.inp là một số nguyên dương M (2<M<2.000.000.000).
Dữ liệu ra: Ghi ra file văn bản
Fibonacci.out gồm 2 dòng
Dòng 1: Dãy Fibonacci nhỏ hơn m tìm được.
Dòng 2: Số Fibonacci nguyên tố lớn nhất tìm được.
FIBONACCI.INP
FIBONACCI.OUT
10
0 1 1 2 3 5 8
5
Ý tưởng: Dùng phương pháp sàng số nguyên tố.
Khởi tạo 1 mảng bool kích thước MAX, với giá trị các phần tử của mảng F
= 0 (giả sử các phần tử trong mảng F là số nguyên tố).
Sàng các số từ 2à MAX
+Nếu (!F[i])=1 thì: i là số nguyên tố,
Ta tạo vòng lặp j=2 đến i*j <=MAX,
F[i*j]=1
để sàng các phần tử là bội của i không phải số nguyên tố.
Khởi tạo các giá trị cho các biến i1,i2,i3 và ghi i1,i2 vào tệp Fibonacci.out.
Dùng vòng lặp for để tìm các số Fibonacci, dùng biến cnt để lưu số Fibonacci nguyên tố lớn nhất tìm được.
+ Vòng for với i chạy từ 3 đến i3<=m
Ghi i3 vào tệp Fibonacci.out
Nếu i3 là số nguyên tố thì cnt =i3.
Sau đó ta tính i3=i1+i2 , i1=i2,	i2=i3
Vòng for dừng lại ta có dãy các số Fibonacci tìm được và số Fibonacci nguyên tố lớn nhất tìm được là cnt.
Chương trình cụ thể như sau:
#include using namespace std;
typedef long long ll; const ll MAX = 1e9; bool F[MAX]={0}; void sangnt()
{ for(ll i = 2; i < MAX; i++)
{if(!F[i])
for(ll j = 2; i*j < MAX; j++) F[i*j] = 1;
}
return ;	} void xl()
{ ll m;
ifstream inp{"fibonacci.inp"};
inp >> m;	ll i1 = 0, i2= 1, cnt , i3 = 1; ofstream out{"fibonacci.out"};
sangnt();
out << i1 << " " << " ";
for(ll i = 3; i3 <= m; i++)
{ out << i3 << " "; if(!F[i3]) cnt = i3; i3 = i1 + i2;
i1 = i2;
i2 = i3;	}
out << "\n" << cnt;	} int main()
{	xl(); return 0;
}
Bài toán 5.	Vòng số nguyên tố
Một vòng tròn chứa 2*n vòng tròn nhỏ. Các vòng tròn nhỏ được đánh số từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*n mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1.
Dữ liệu vào: Từ File văn bản Vongtron.inp là một số nguyên dương n ( 1 < n < 10 ) .
Dữ liệu ra: Ghi ra File văn bản vongtron.out dòng đầu tiên ghi ra số k là số cách tìm được. K dòng tiếp theo mỗi dòng ghi ra 1 cách điền các số vào các vòng tròn nhỏ. Cách điền nào có thứ tự từ điển nhỏ hơn thì xếp trước. Nếu K > 10000 thì chỉ cần ghi ra 10000 cách đầu tiên.
Vongtron.inp
Vongtron.out
4
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Ý tưởng:
+ Dùng phương pháp sàng nguyên tố
+ Áp dụng thuật toán quay lui để chọn các số, kiểm tra điều kiện dựa trên mảng sàng nguyên tố.
Chương trình cụ thể như sau:
#include using namespace std; const int MAX = 30;
int N = 0; int total = 0;
int a[MAX], check[MAX]; bool isEnough = false; string result = "";
int isPrime[2*MAX]; void sieve()
{ const int BOUND = (int)sqrt(2*MAX); for (int i = 2; i <= BOUND; ++i) {
if (isPrime[i] == 0) {
for (int j = 2*i; j <= 2*MAX; j += i) { isPrime[j] = 1;
}	}	}
}
void backtracking(int k) { if (k > N) {
if (isPrime[a[k-1] + 1] == 1) return;
if (++total > 10000) {
--total; isEnough = true; return;	}
for (int i = 1; i <= N; ++i) result += to_string(a[i]) + " "; result += "\n";
return;	}
for (int i = 2; i <= N; ++i) { if (check[i] == 0) {
check[i] = 1;	a[k] = i;
if (isPrime[a[k] + a[k-1]] == 0) backtracking(k + 1);
if (isEnough) return; check[i] = 0;
}	} }
int main()
{ifstream inp("vt.inp"); ofstream out("vt.out"); int n; inp >> n;
isPrime[0] = isPrime[1] = 1; sieve();
a[1] = 1;
N = 2*n; backtracking(2);
out << total << "\n" << result; return 0; }
Bài toán 6:	Dãy số đặc biệt
(Đề thi HSG tỉnh Nghệ An năm học 2009-2010)
Dãy số A1,A2,...,An được gọi là dãy số đặc biệt nếu nó thỏa mãn các điều kiện sau:
Là dãy số giảm dần.
Với mỗi A thì A’ hoặc là số nguyên tố hoặc là ước của một trong các số từ A1 đến Ai-1.
Em hãy tìm dãy số đặc biệt dài nhất bắt đầu từ N.
Dữ liệu vào: Từ File văn bản DAYSO.INP là một số nguyên dương N (N<10000)
Dữ liệu ra: Ghi ra File văn bản DAYSO.OUT là dãy số tìm được các số cách nhau bởi dấu cách.
DAYSO.INP
DAYSO.OUT
12
12 11 7 6 5 4 3 2 1
Ý tưởng:
Tìm các số thõa mãn điều kiện là số nguyên tố hoặc là ước của N ghi vào tệp DAYSO.OUT.
Dùng kiểu dữ liệu Set để lưu dãy số cần tìm.
Set st;
Khởi tạo mảng bool gồm N+1 phần tử, các phần tử của mảng có giá trị =0 (Giả sử tất cả các phần tử trong mảng f là số nguyên tố).
Dùng phương pháp sàng nguyên tố:
+ Xét i chạy từ: 1àN
Nếu N chia hết cho i thì đưa i vào tập hợp st.
Nếu !f[i]=1 thì i là số nguyên tố, ta đưa i vào tập st.
Dùng vòng for với j chạy từ 2 đến i*j <=N, loại bỏ các phần tử là bội của i, f[i*j]=1 (phần tử không phải số nguyên tố).
-	Thêm 1 vào tập hợp st, viết các phần tử
của
tập
hợp
st
vào
tệp:
DAYSO.OUT theo thứ tự từ cuối về đầu.






Chương trình cụ thể như sau:






#include 






using namespace std;






void xl()






{ int n;






ifstream inp{"DAYSO.INP"}; ofstream out{"DAYSO.OUT"};
inp >> n;	set st;	bool f[n +1] = {0}; for(int i = 2; i <= n; i++)
{	if(n % i == 0) st.insert(i); if(!f[i])
{	st.insert(i);
for(int j = 2; i*j <= n; j++) f[i*j] = 1; }
}
st.insert(1);
for(auto it = st.rbegin(); it != st.rend(); it++) out << *it <<" ";	}
int main()
{ xl(); return 0;
}
Bài toán 7.	Biểu diễn số
Cho một số nguyên k, hãy tìm cách biểu diễn k thành tổng 3 số nguyên tố đôi một khác nhau.
Dữ liệu : Vào từ file văn bản PRIME.INP chứa duy nhất 1 số là k (15<=k<=2.000.000.000).
Kết quả : Ghi ra file văn bản PRIME.OUT gồm 3 số nguyên tố đôi một khác nhau và có tổng là k.
Ví dụ :
PRIME.INP
PRIME.OUT
20
2 19 79
Ý Tưởng:
+ Dùng phương pháp sàng nguyên tố
+Chia hai trường hợp để giải, n lẻ và chẵn
+ Ta dùng giả thuyết Goldback sau để giải: Mọi số nguyên lẻ đều có thể phân tích thành tổng của 2 số nguyên tố (đã được kiểm chứng đến 4*10^18).
+ Trong trường hợp n lẻ, ta có nhận xét sau: khoảng cách giữa các số nguyên tố liên tiếp nhau là không quá lớn, trong phạm vi 10^9, khoảng cách tối đa chỉ gần
300. Vì vậy ta xét từ n-300 đến n để tìm số thứ nhất trong tổng. Sau đó, ta brute force để tìm hai số còn lại do tổng của chúng lẻ, tức luôn tồn tại.
+ Độ phức tạp 300.căn (n).
+ Trong trường hợp n chẵn, tổng phải luôn tồn tại 2, nên phần còn lại là n-2 ta dùng cách brute force để tìm hai số còn lại. Test trong phạm vi 40000000 luôn tìm được với thời gian rất nhanh.
Chương trình cụ thể như sau:
#include using namespace std; const int N = 35000000;
int cal[N + 2], isPrime[N + 2]; vector prime;
void sievePrime() {
for (int i = 2; i <= N; ++i) { if (cal[i] == 0) {
cal[i] = i; prime.emplace_back(i); isPrime[i] = 1;	}
for (int j = 0; j < prime.size() && prime[j] <= cal[i] && i * prime[j] <= N;
++j) {
cal[i * prime[j]] = prime[j];
}	}	}
void solve(int n) { if (n % 2 != 0) {
int firstNum = 0, sum = 0; for (int i = n - 1; i >= 2; --i) { if (isPrime[i]) {
firstNum = i;
sum = n - i;
for (int i = 0; i < prime.size() && prime[i] <= n / 2; ++i) { const int temp = sum - prime[i];
if (temp > 0 && isPrime[temp] && temp != prime[i]) {
cout << firstNum << " " << prime[i] << " " << sum - prime[i]; return;
}	}
}
}
} else
{
const int firstNum = 2, sum = n - 2;
for (int i = 0; i < prime.size() && prime[i] <= n / 2; ++i) { const int temp = sum - prime[i];
if (isPrime[temp] && temp != prime[i])
{
cout << firstNum << " " << prime[i] << " " << sum - prime[i]; return;
}
}
}
}
int main()
{	freopen("DLM.INP", "r", stdin);
freopen("DLM.OUT", "w", stdout); cin.tie(0);
int n;
cin >> n; sievePrime(); solve(n); return 0;
}
Bài toán 8:	Dãy nguyên tố
(Đề thi học sinh giỏi tỉnh Nghệ An năm học 2014-2015)
Cho số tự nhiên k và dãy A gồm N (N < 104) số tự