Bàn về 1 thuật toán kiểm tra sự nguyên tố

Chào các bạn! Bài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.

Có rất nhiều cách, các cách thông thường là:

  • Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
  • Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!

Có một cách nhanh hơn nữa.

Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như hai cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo một quy luật nào đó. Quy luật đó là gì?

Nhận xét: một số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.

Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ một số nào trong đó thì N là hợp số, trái lại N là nguyên tố.

int check(int N) {
    int x, y, t;
    if (N < 2) return 0;
    if (N == 2 | N == 3) return 1;
    if (N % 2 == 0 | N % 3 == 0) return 0;
    x = 5; y = 2;
    t = (int)sqrt((double)N);
    while (x <= t) {
        if (N % x == 0) return 0;
        x += y;
        y = 6 - y;
    }
    return 1;
}
Advertisements

4 thoughts on “Bàn về 1 thuật toán kiểm tra sự nguyên tố

  1. 49 khong phai la so nguyen to :
    int Nt (int n)
    {
    int i, Kq;
    double m;

    if ( n <= 1)
    Kq = 0;
    else
    {
    Kq = 1;
    i = 2;
    m =(int)sqrt( (double) n);
    while (i <=m && Kq)
    {
    if( n % i == 0)
    Kq = 0;
    i++;
    }
    }
    return Kq;
    }

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s