Dãy nguyên tố | Câu 2 - Đề HSG tin 11 Nghệ An | Năm 2014 - 2015

Bài 2. (6 điểm) Dãy nguyên tố                                                                
Cho số tự nhiên k và dãy A gồm N (N < 10⁴) số tự nhiên không vượt quá 32000.
Yêu cầu: Tìm k số nguyên tố nhỏ nhất khác nhau xuất hiện trong dãy A.
Dữ liệu vào từ file văn bản DAYNT.INP:

• Dòng đầu tiên chứa một số tự nhiên k (1 < k < N).
• N dòng tiếp theo, mỗi dòng chứa một số tự nhiên là một phần tử của dãy A.

Kết quả ghi ra file văn bản DAYNT.OUT: Đưa ra trên cùng một dòng k số nguyên tố tìm được theo thứ tự tăng dần, các số cách nhau ít nhất một ký tự trống.
Lưu ý: Dữ liệu vào đảm bảo luôn tìm được k số nguyên tố thỏa mãn.
Ví dụ:

DAYNT.INP	DAYNT.OUT
3 12 13 17 9 3 1 12	3 13 17

Code mẫu bằng Pascal 1:

CONST   fi      =       'DayNT.inp';
        fo      =       'DayNT.out';
Var     D : Array[2..32000] of byte;
        i,n,k,a : integer;
Procedure       mofile;
begin
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
end;
Function        Nto( n : integer): boolean;
var     i :integer;
begin
        if n<2 then exit(false)
        else
        for i:=2 to trunc(sqrt(n)) do
                if n mod i =0 then exit(false);
        exit(true);
end;
Procedure       Doc_xuly;
begin
       readln(k);
       for i :=1 to 32000 do d[i] :=0;
        while not seekeof do
                begin
                        readln(a);
                        if nto(a) then d[a] :=1;
                end;
end;
Procedure       xuat;
begin
            n:=0;
            for i :=1 to 32000 do
             if d[i]<> 0 then
                begin write(i,' ');
                      n := n+1;
                      if n = k then exit;
                end;

end;
Begin
       mofile;
       Doc_xuly;
       xuat;
end.

Giải thích:

Chương trình trên là một kỹ thuật xử lý dãy số nguyên tố bằng cách dùng mảng đánh dấu, nhằm tránh việc phải sắp xếp mảng trước khi xử lý. Ngoài ra cách xử lý bài trên cũng được tinh gọn bằng cách vừa đọc dữ liệu vử xử lý luốn, nên cũng cải thiện được hiểu suất của thuật toán. Đọc đến số nào thì kiểm tra xem số đó có phải là số nguyên tố hay không, nếu a là số nguyên tố thì gán luôn d[a] = 1. Ngoài ra đây cũng là cách mà chỉ sử dụng biến a và mảng đánh dấu d nhằm tối thiểu bộ nhớ biến.

Procedure       Doc_xuly;
begin
       readln(k);
       for i :=1 to 32000 do d[i] :=0;
        while not seekeof do
                begin
                        readln(a);
                        if nto(a) then d[a] :=1;
                end;
end;

Với cách xử lý như trên ta thấy code vừa gọn, tối ưu được thuật toán và bộ nhớ.
Như các bạn đã biết, trong Pascal thì việc sắp xếp mảng không có hàm xây dựng sẵn, nên khi sắp xếp thì các bạn cần phải viết code để sắp xếp. Để hiểu hơn về sự tinh gọn của code trên, mời các bạn tham khảo thêm code mẫu sau để hiểu thêm về thuật toán sắp xếp quicksort :

Code mẫu bằng Pascal 2:

const   fi='DAYNT.inp';
        fo='DAYNT.out';
var     f:text;
        n,i,j,m:longint;
        k:array[0..32767] of boolean;
        a,b:array[1..10000000] of longint;
procedure       docf;
begin
        assign(f,fi);
        reset(f);
        n:=0;
        readln(f,m);
        while not eof(f) do
        begin
                inc(n);
                readln(f,b[n]);
        end;
        close(f);
end;
function        nt(i:longint):boolean;
var     j:longint;
begin
        nt:=false;
        if i=1 then exit;
        if i=0 then exit;
        for j:=2 to trunc(sqrt(i)) do if i mod j=0 then exit;
        nt:=true;
end;
procedure       td(var a,b:longint);
var tg:longint;
begin
        tg:=a;a:=b;b:=tg;
end;
procedure       qs(l,r:longint);
var x,i,j:longint;
begin
        x:=a[(l+r)div 2];
        i:=l;j:=r;
        repeat
        while a[i]<x do inc(i);
        while a[j]>x do dec(j);
        if i<=j then
        begin
                td(a[i],a[j]);
                inc(i);dec(j);
        end;
        until i>j;
        if l<j then qs(l,j);
        if i<r then qs(i,r);
end;
procedure       xd;
begin
        for i:=1 to n do if not k[b[i]] then
        begin
                k[b[i]]:=true;
                if nt(b[i]) then
                begin
                        inc(j);
                        a[j]:=b[i];
                end;
        end;
end;
begin
        docf;
        assign(f,fo);
        rewrite(f);
        xd;
        qs(1,j);
        for i:=1 to m do write(f,a[i],' ');
        close(f);
end.

Giải thích:

So với code mẫu 1 thì trong code mẫu 2 này các bạn thấy bài này phải sử dụng tới 3 mảng, trong khi code mẫu 1 chỉ sử dụng 1 biến mảng. Đồng thời trong code mẫu 1 không cần sử dụng thuật toán sắp xếp. 

Lời giải bằng Python:

#Hàm Kiểm tra nguyên tố.
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# Đọc dữ liệu vào từ file DAYNT.INP
with open("DAYNT.INP", "r") as f:
    k = int(f.readline())
    a = [int(line.strip()) for line in f]

# Tìm k số nguyên tố nhỏ nhất trong dãy số a
primes = []
num_primes_found = 0
for num in sorted(a):
    if is_prime(num):
        primes.append(num)
        num_primes_found += 1
        if num_primes_found == k:
            break

# Ghi kết quả vào file DAYNT.OUT
with open("DAYNT.OUT", "w") as f:
    f.write(" ".join(str(x) for x in primes))

 Giải thích:

Đối với Python thì việc sắp xếp đã có phương thức sẵn nên ta sử dụng sắp xếp mảng đầu vào trước, sau đó dùng hàm kiểm tra số nguyên tố để tìm đủ k số nguyên tố đầu tiến, khi tìm đủ k số nguyên tố đầu tiên thì ta thoát khỏi vòng lặp for bằng lệnh break. Trong code trên ta thấy cũng cần phải có 2 biến mảng để lưu dữ liệu, tuy nhiên các bạn có thể sử dụng kỹ thuật giống code mẫu 1 để giảm đi 1 biết mảng. Các bạn hãy thử code lại bằng python xem sao nhé.

Link tải các test:

Mình để link tải các test dưới bài viết nhé, các bạn code lại và chạy với các test dưới, nếu chạy full test thì chúc mừng các bạn đã đạt full điểm bài này.