//
you're reading...
01 - Chủ đề thuật toán, Dùng cho cấp THCS, Dùng cho cấp THPT

Thuật toán kiểm tra số nguyên tố

1. Bài toán


Cho một số n, kiểm tra xem đó có phải là số nguyên tố hay không.

2. Giải thuật 1:


– Nếu n là 1, thì n không là số nguyên tố
– Xét tất cả số nguyên x nhỏ hơn (n – 1), kiểm tra xem n có chia hết x không, nếu tất cả không thì n là số nguyên tố.

3. Giải thuật 2:


Chúng ta có thể nhận thấy rằng giải thuật 1 kiểm tra số nguyên tố có số lần lặp tuỳ thuộc vào giá trị của n, nếu n quá lớn, hệ thống sẽ tính toán với thời gian lâu tương ứng, vì thuật toán đó theo cơ chế quét cạn.
Chúng ta sẽ tối ưu thuật toán này theo giải thuật 2:
– Nếu n là 1, thì n không là số nguyên tố
– Nếu n là 2, thì n là số nguyên tố
– Nếu n chia hết cho 2, thì n không là số nguyên tố
– Xét tất cả các số lẻ x từ 3 đến √n, nếu n chia hết cho x thì n không là số nguyên tố
– Khi xét hết mà không chia hết thì xuất ra n là số nguyên tố

4. Giải thuật 3:


-Nếu n là 1 thì N không nguyên tố.
-Nếu n > 1 và n<4 thì n là số nguyên tố
– Xét tất cả các số 2 đến √n, nếu n chia hết cho x thì n không là số nguyên tố
– Khi xét hết mà không chia hết thì xuất ra n là số nguyên tố.
songuyent

5. Bài giải minh họa bằng Pascal


var
        N,i: longint;
begin
repeat
         write('Nhap N= ');
         readln(N);
until (N>0);
if (N=1) then
         writeln(N,' khong la so nguyen to.')
else
         if (N<4) then
                writeln(N,' la so nguyen to.')
        else
                begin
                        i:= 2;
                        while i<= trunc(sqrt(N)) do
                                 if (N mod i = 0) then
                                         begin
                                               writeln(N,' khong la so nguyen to.');
                                               exit;
                                         end
                                else inc(i);
                        if i> trunc(sqrt(N)) then
                               writeln(N,' la so nguyen to.');
                 end;
readln;
end.

6. Độ phức tạp của thuật toán giải thuật tìm số nguyên tố


Độ phức tạp của thuật toán 2 là O(√n / ln(n)).

7. Giải thuật4 :


 B0  Bắt đầu
B1  Nhập số N
B2  N = 1 thì chuyển sang bước B 9
B2  Nếu N=2 hoặc N=3 thì chuyển sang B8
B3  Gán i :=-1
B4  Nếu (N mod 2 =0) hoặc  (N Mod 3 =0) thì  chuyển sang B 9
B5  Tăng i lên 6 đơn vị
B6  Nếu (N mod i <> 0) và (N mod (i+2) <>0)  và ( i*i <= N ) chuyển sang B 5
B7  Nếu i*i <= N  thì  chuyển sang B 9
B8  Thông báo  : N là số nguyên tố , chuyển tới B10
B9  Thông báo  : N không là  số nguyên tố
B10 Kết thúc chương trình


Bài đọc thêm


  • Bài toán số nguyên tố

  • Advertisements

    About pascalteacher

    Trang thông tin Toán học và Tin học

    Thảo luận

    Không có bình luận

    Trả lời

    Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

    WordPress.com Logo

    Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

    Twitter picture

    Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

    Facebook photo

    Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

    Google+ photo

    Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

    Connecting to %s

    Các tác giả

    Categories

    Tháng Tám 2015
    H B T N S B C
    « Th1   Th9 »
     12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31  

    NCT Computer

    Flickr Photos

    Thống kê

    • 179,899 lượt xem

    pascalteacher.nct@gmail.com


    Trang huấn luyện học sinh giỏi Tin học

    %d bloggers like this: