Xem mã nguồn của Chia thử

'''Chia thử''' hay '''Chia thử nghiệm''' là cách làm tốn công nhưng đơn giản dễ hiểu nhất trong các thuật toán [[phân tích số nguyên]] ra thừa số. Ý tưởng của phương pháp này là thực hiện hàng loạt các phép chia để xem với số nguyên ''n'' có chia hết cho lần lượt từng số tự nhiên nhỏ hơn [[giá trị tuyệt đối]] của ''n'' hay không. Ví dụ với {{Math|n {{=}} 12}} sẽ chia hết cho 1, 2, 3, 4, 6, 12. Tối giản thành các thừa số [[Sức mạnh nguyên tố|số nguyên tố]] sẽ thu được {{Math|12 {{=}} 3 × 4 {{=}} 3 × 2<sup>2</sup>}} .

Chia thử được [[Fibonacci]] lần đầu tiên mô tả trong cuốn ''[[Liber Abaci]]'' (1202).<ref>{{Chú thích tạp chí|last=Mollin|first=Richard A.|year=2002|title=A brief history of factoring and primality testing B. C. (before computers)|url=https://archive.org/details/sim_mathematics-magazine_2002-02_75_1/page/18|journal=Mathematics Magazine|volume=75|issue=1|pages=18–29|doi=10.2307/3219180|mr=2107288}}</ref>

== Phương pháp ==
Cho trước một số nguyên dương ''n'', cách chia thử sẽ kiểm tra một cách có hệ thống xem ''n'' có chia hết cho bất kỳ số nhỏ hơn ''n''. Phép thử sẽ lấy tăng dần số chia ''k'' bắt đầu từ 2 trở lên. Nếu ''n'' không chia hết cho ''k'' thì cũng không chia hết cho các bội số của ''k'' và sẽ không cần kiểm tra, ví dụ nếu đã không chia hết cho 2 thì không cần thử phép chia với 4 hoặc 6. Như vậy, phép thử có thể được giảm bớt khi chọn số chia là [[số nguyên tố]]. Ngoài ra, số chia cũng chỉ cần thử khi nhỏ hơn <math>\scriptstyle\sqrt{n}</math> vì nếu ''n'' chia hết ''p'', thì ''n = p × q'' và nếu ''q'' nhỏ hơn ''p'' thì đã được phát hiện khi cho ''q'' rồi. Nếu ''n'' là [[số chính phương]] thì căn bậc hai của ''n'' cũng là một thừa số dùng làm giới hạn trên cho phép thử.

Cũng có thể dùng thừa số nguyên tố để xác định giới hạn thử nghiệm chặt hơn. Giả sử {{Mvar|P<sub>i</sub>}} là số nguyên tố thứ {{Mvar|i}}, nghĩa là ''P'' <sub>1</sub> = 2, ''P'' <sub>2</sub> = 3, ''P'' <sub>3</sub> = 5,... Nếu {{Mvar|P<sub>i</sub>}} là số cuối cùng dùng trong phép thử cho ''n'' thì {{Math|''P''<sup>2</sup><sub>''i''&nbsp;+&nbsp;1</sub> > ''n''}}  nên {{Math|''P''<sub>''i''&nbsp;+&nbsp;1</sub>}} chính là giới hạn không cần thử. Ví dụ ''n'' = 48 thì chỉ cần thử chia cho 2, 3 và 5 là đủ vì [[bình phương]] của số nguyên tố tiếp theo là {{Math|1=''P''<sup>2</sup><sub>4</sub> =7<sup>2</sup>=49}} lớn hơn 48 rồi, hoặc ''n'' < 25 thì chỉ cần thử chia cho 2 và 3 là đủ.

Đây là một ví dụ của thuật toán chia thử, sử dụng các số tự nhiên liên tiếp thành các số để thử, như sau (trong Python):

<syntaxhighlight lang="python">
def trial_division(n: int) -> List[int]:
    """Trả ra một danh sách các thừa số nguyên tố cho một số tự nhiên."""
    a = []               # Chuẩn bị một danh sách trống.
    f = 2                # Ước số có thể đầu tiên.    
    while n > 1:         # Khi n vẫn còn ước số...
        if n % f == 0:   # Số dư là n chia cho f có thể là 0.        
            a.append(f)  # Nếu cho n chia cho nó, ra kết quả 0. Thêm f vào danh sách.
            n //= f       # Chia ước số trên cho n.
        else:            # Nếu n không phải ước của n,
            f += 1       # Thêm 1 vào f và thử lại.
    return a             # Các ước nguyên tố có thể lặp lại: 12 phân tích ra 2,2,3.
</syntaxhighlight>
Cách khác hiệu quả hơn gấp đôi:

<syntaxhighlight lang="python">
def trial_division(n: int) -> List[int]:
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
    # Chỉ có số lẻ là có thể
    return a
</syntaxhighlight>

Cách chia thử như thế này được đảm bảo tìm ra tất cả ước số của ''n'', nếu ''n'' là số nguyên tố thì phép thử có thể chạy đến ''n''. Do đó, nếu thuật toán chỉ tìm thấy một ước số (lớn hơn 1) thì chứng tỏ ''n'' là [[số nguyên tố]]. Nếu tìm thấy nhiều hơn thì ''n'' là [[hợp số]].

== Tham khảo ==
{{tham khảo}}

* {{Chú thích sách|title=A concrete introduction to higher algebra|last=Childs|first=Lindsay N.|publisher=[[Springer-Verlag]]|year=2009|isbn=978-0-387-74527-5|edition=3rd|series=[[Undergraduate Texts in Mathematics]]|location=New York, NY|zbl=1165.00002}}
* {{Chú thích sách|title=Prime numbers. A computational perspective|url=https://archive.org/details/primenumberscomp0002cran|last=Crandall|first=Richard|last2=Pomerance|first2=Carl|publisher=[[Springer-Verlag]]|year=2005|isbn=0-387-25282-7|edition=2nd|location=New York, NY|zbl=1088.11001|author-link=Richard Crandall|author-link2=Carl Pomerance}}

== Liên kết ngoài ==
* [https://betaprojects.com/calculators/prime_factors.html Phân tích thừa số nguyên tố nhanh dùng JavaScript bằng chia thử] {{Webarchive|url=https://web.archive.org/web/20211218090226/https://betaprojects.com/calculators/prime_factors.html |date=2021-12-18 }}.{{en}} Có thể xử lý các số lên đến khoảng 2<sup>53</sup>
* [https://www.blogcyberini.com/2018/04/algoritmo-fatoracao-de-numeros-inteiros-divisao-por-tentativa.html Chia thử bằng Java, C và JavaScript] {{pt}}

[[Thể loại:Phép chia]]