Tìm số nguyên tố với regular expression
research
7
White

huydx viết ngày 09/09/2016

alt text

Cách đây tương đối lâu, có một đoạn trao đổi trên PERL mailing list:

http://diswww.mit.edu/bloom-picayune.mit.edu/perl/10138

Có một hacker tên là Abigail đã đưa ra một đoạn code sử dụng regular expression (Regexp) để ... tìm số nguyên tố. Chắc bạn nào nghe xong cũng khá ngạc nhiên, regexp lại dùng được để tìm số nguyên tố :)).
Để đỡ dài dòng tôi sẽ đi luôn vào vấn đề chính, đoạn regex đó như sau:

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/'

Có lẽ không mấy bạn biết perl nên tôi viết lại đoạn code trên bằng ruby:

while(a = gets) do
  if /^1?$|^(11+?)\1+$/.match "#{'1'*a.to_i}"
    puts "not prime"
  else
    puts "prime"
  end
end

Vậy làm thế nào mà đoạn code trên tìm được số nguyên tố, chúng ta hãy bắt đầu nào:

  • Đầu tiên chúng ta sẽ biến input đầu vào (N) thành 1 chuối N các số 1

9 => "111111111"
2 => "11"
1 => "1"

Điều này được thực hiện thông qua đoạn code:

"#{'1'*a.to_i}" 

Tiếp đó việc "match" chuỗi N số 1 này với regexp

/^1?$|^(11+?)\1+$/.

sẽ cho ta biết N có phải là số nguyên tố hay không.
Hãy phân tích regexp trên thành 2 phần

  • phần 1: ^1?$
  • phần 2: ^(11+?)\1+$

Như chúng ta đã thấy 2 phần này được nối với nhau bởi kí tự or | , trong regex A|B thì nghĩa là match A hoặc match B.
Từ đấy chúng ta sẽ thấy chuỗi nào match phần 1 hoặc phần 2, sẽ không phải là số nguyên tố.

Phần 1: ^1?$

Phần này rất dễ hiểu:
^ là kí tự match với đầu dòng, $ là kí tự match với kết dòng, 1? nghĩa là có 1 chữ 1 hoặc không có chữ nào cả.
Kết hợp lại với nhau chúng ta sẽ có kết quả là khi kết quả đầu vào là "1" hoặc 1 chuỗi rỗng, sẽ match với phần 1. Và hiển nhiên 1 và 0 không phải là số nguyên tố nên điều này đúng.
Nếu chuỗi đầu vào có nhiều hơn 1 chữ "1", thì phần 2 sẽ được bắt đầu match.

Phần 2: ^(11+?)\1+$

Phần này cũng bắt đầu với 1 kí tự match đầu dòng ^
Tiếp theo chúng ta có (11+?). Đoạn này có nghĩa là

group một đoạn có từ 2 số 1 trở lên, bắt đầu từ group nhỏ nhất

Đề hiểu được đoạn này các bạn chỉ cần nắm được 2 khái niệm trong regex về:

Dấu ngoặc có nghĩa là "capture" lại 1 cụm, để dành dùng sau,
Còn đoạn 1+ nghĩa là "match với số 1 lặp lại lớn hơn 1 lần".

Như thế giả sử input của chúng ta là "111111" (6 số 1), thì đoạn ^(11+?) trong lần đầu tiên sẽ match 2 chữ "1" đầu tiên , và nhóm thành 1 cụm, mình gọi tạm là cụm X:

"(11)1111" (X = "11")

Và đoạn regex còn lại \1+$ theo chính là point làm nên việc có thể tìm được số nguyên tố:
Để hiểu được đoạn này các bạn chỉ cần nắm được khái niệm

  • backrefrenced và sử dụng lại khái niệm về repetition đã có ở trên.

Backreference có nghĩa là, sử dụng "cụm" đã được group ở trước để match, với kí hiệu cho backreference là kí tự \. Và ở đây \1 có nghĩa là cụm đầu tiên được group.
Trong trường hợp chúng ta đang ví dụ, thì nó chính là cụm X mà mình vừa mới tạm gọi ở trên, hiện đang có giá trị là 11.

TIếp theo sau \1+, có nghĩa là cụm X được lặp lại N lần. Như vậy lấy ví dụ với 6 số 1 ở trên, thì đoạn \1+$ sẽ match với 4 số 1 còn lại + kí tự hết dòng, bởi vì 4 chia hết cho 2 là số kí tự của cụm X, do đó cụm X được lặp lại 2 lần việc match sẽ thành công.

"(11)<(11)(11)>"

Việc match như vậy có nghĩa là số kí tự số 1 đầu vào sẽ chia hết cho một số N nào đó lớn hơn hoặc bằng 2, hay suy ra khi đó đầu vào không phải là 1 số nguyên tố!

Abigail quá thông minh phải không!

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

115 bài viết.
858 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
135 8
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết hơn 1 năm trước
135 8
White
109 14
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết gần 3 năm trước
109 14
White
86 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết hơn 2 năm trước
86 10
Bài viết liên quan
White
11 1
Introduction Trong (Link), chúng ta đã tìm hiểu sơ qua về khái niệm Full Text Search, cũng như về Inverted Index. Qua bài viết đầu tiên, các bạn ...
huydx viết gần 3 năm trước
11 1
White
7 5
Introduction Trong (Link), các bạn đã được tìm hiểu về việc sử dụng Boolean Logic để tìm ra các Document chứa các term trong query cần tìm kiếm. ...
huydx viết gần 3 năm trước
7 5
White
1 1
Dẫu kĩ sư phần mềm không phải là cử nhân khoa học máy tính, nhưng để hiện thực hoá cái gì đó chuyên sâu chưa có sẵn thư viện, kĩ sư vẫn cứ phải đọc...
Ngoc Dao viết gần 2 năm trước
1 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
858 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!