4.5 Biprime Cặp số tự nhiên x và số lật của nó, x' nếu đồng thời là hai số nguyên tố khác nhau thì được gọi là cặp song nguyên tố. Hãy liệt kê các cặp song nguyên tố trong khoảng 1..N = 500000. biprime.inp | biprime.out | Giải thích Input text file: số N Output text file: Dòng đầu tiên: M – số cặp song nguyên tố. Tiếp đến là M dòng, mỗi dòng một cặp song nguyên tố. Với n = 100 ta tìm được 4 cặp song nguyên tố: (13, 31), (17, 71), (37, 73) và (79, 97). Các số cùng dòng cách nhau qua dấu cách. | 100 | 4 13 31 17 71 37 73 79 97 |
Thuật toán
Trước hết dùng thuật toán sàng để tìm và ghi nhận các số nguyên tố trong khoảng 1..N. Dùng mảng a đánh dấu các số nguyên tố. Nếu bit thứ i bằng 0 thì i là số nguyên tố. Các thủ tục xử lí bit bao gồm: BitOn(i): Đặt bit thứ i trong a bằng 1 (bật bit i); BitOf(i): Đặt bit thứ i trong a bằng 0 (tắt bit i); GetBit(i): cho giá trị 0/1 của bit thứ i trong dãy bit a. Với Nmax = 500000 thì mảng a có kích thước (Nmax+7)/8 = 625000 byte. Bit thứ i trong dãy a sẽ ứng với bit thứ i%8 trong byte b = i/8. Chú ý rằng i%8 = i&7 và i/8 = (i>>3). Sau khi gọi thủ tục Sang ta duyệt lại dãy bit a, với mỗi số nguyên tố i (GetBit(i)=0) ta tìm số lật ip = Rev(i). Nếu ip ≠ i, ip N và ip cũng là số nguyên tố thì ta đếm số cặp. Ta sử dụng bảng quyết định để xác định khi nào thì cần đánh dấu (đặt BitOn(i) hoặc BitOn(ip)). Nếu i và số lật ip của nó là cặp song nguyên tố thì ta chỉ cần đánh dấu một trong hai số đó bằng thủ tục BitOn. Lần duyệt thứ hai ta chỉ quan tâm những bit i nhận giá trị 0 và ghi lại các cặp i và Rev(i).
Bảng quyết định xóa i và số lật | ip = Rev(i). Xóa x tức là đặt BitOn(x). | Điều kiện | i nguyên tố | yes | yes | yes | yes | ip N | yes | yes | yes | No | ip ≠ i | yes | yes | no | | ip nguyên tố | yes | no | | | Quyết định | Xóa i (BitOn(i)) | no | yes | yes | yes | Xóa ip (BitOn(ip)) | yes | no | no | No |
Độ phức tạp
Thủ tục sàng đòi hỏi  phép chia dư và n lần duyệt cho mỗi số nguyên tố do đó bài toán đòi hỏi độ phức tạp tính toán cỡ n.
(* Biprime.pas *)
uses crt;
const mn = (500000+7) shr 3;
fn = 'biprime.inp'; gn = 'biprime.out';
bl = #32; nl = #13#10;
type mb1 = array[0..mn] of byte;
var a: mb1;
procedure BitOn(i: longint); { bật bit i }
var p, b: longint;
begin
b := i shr 3; p := i and 7;
a[b] := a[b] or (1 shl p);
end;
procedure BitOff(i: longint); { tắt bit i }
var p, b: longint;
begin
b := i shr 3; p := i and 7;
a[b] := a[b] and (not(1 shl p));
end;
function GetBit(i: longint): integer; { nhận giá trị của bit i }
var p,b: longint;
begin
b := i shr 3; p := i and 7;
GetBit := (a[b] shr p) and 1;
end;
procedure Sang(n: longint);
var i,j: longint;
begin
fillchar(a,sizeof(a),0);
for i := 2 to round(sqrt(n)) do
if GetBit(i) = 0 then
for j := i to (n div i) do BitOn(i*j);
end;
function Rev(x: longint): longint; { số lật của x }
var y: longint;
begin
y := 0;
while x <> 0 do
begin
y := y*10 + (x mod 10);
x := x div 10;
end;
Rev := y;
end;
function Doc: longint;
var n: longint;
f: text;
begin
assign(f,fn); reset(f);
readln(f,n); close(f);
Doc := n;
end;
procedure Run;
var n, i, ip, d: longint;
g: text;
begin
n := Doc;
Sang(n);
d := 0;
for i := 13 to n do
if GetBit(i) = 0 then { i nguyên tố }
begin
ip := Rev(i);
if (ip <= n) and (ip <> i) then
begin
if GetBit(ip) = 0 then { ip nguyên tố }
begin
inc(d);
BitOn(ip); { xóa ip }
end else BitOn(i); { xóa i }
end else BitOn(i);
end;
{ Ghi file }
assign(g,gn); rewrite(g);
writeln(g,d);
for i := 13 to n do
if GetBit(i) = 0 then
writeln(g,i,bl,Rev(i));
close(g);
end;
BEGIN
Run;
write(nl,' Fini'); readln;
END.
// Devcpp biprime.cpp
#include
#include
#include
using namespace std;
// D A T A A N D V A R I A B L E
const char * fn = "biprime.inp";
const char * gn = "biprime.out";
const int mn = (500000+7)>>3;
char a[mn];
// P R O T O T Y P E S
int main();
int Doc();
void BitOn(int i);
void BitOff(int i);
int GetBit(int i);
int Rev(int x);
void Sang(int n);
void Run();
// I M P L E M E N T A T I O N
int main() {
Run();
cout << endl << endl << " Fini ";
cin.get();
return 0;
}
int Doc() {
int n;
ifstream f(fn);
f >> n;
f.close();
return n;
}
void BitOn(int i) { // bật bit i
int b = i >> 3, p = i & 7;
a[b] |= (1 << p);
}
void BitOff(int i) { // tắt bit i
int b = i >> 3, p = i & 7;
a[b] &= ~(1 << p);
}
int GetBit(int i) { // nhận trị của bit i
int b = i >> 3, p = i & 7;
return (a[b] >> p) & 1;
}
int Rev(int x) { // số lật của x
int y = 0;
do {
y = y*10 + (x % 10);
x /= 10;
} while (x);
return y;
}
void Sang(int n) {
int can = int(sqrt(n));
int i, j, ni;
for (i = 2; i <= can; ++i)
if (GetBit(i) == 0)
for (ni = n/i, j = i; j <= ni; ++j) BitOn(i*j);
for (i = 13; i <= n; ++i)
if (GetBit(i) == 0) cout << i << " ";
}
void Run() {
int i , n, d, ip;
n = Doc();
memset(a, 0, sizeof(a));
cout << endl << " n = " << n << " mn = " << mn << endl;
Sang(n);
for (d = 0, i = 13; i <= n; ++i)
if (GetBit(i) == 0) {
ip = Rev(i);
if ((ip <= n) && (ip != i)) {
if (GetBit(ip) == 0) {
++d; BitOn(ip); // xóa ip
} else BitOn(i); // xóa i
} else BitOn(i); // xóa i
}
// Ghi file
ofstream g(gn);
g << d << endl;
for (i = 13; i <= n; ++i)
if (GetBit(i) == 0)
g << i << ' ' << Rev(i) << endl;
g.close();
}
Chia sẻ với bạn bè của bạn: |
