Hãy cung cấp một số nguyên để tìm các hệ số nguyên và cây hệ số.
Số nguyên tố là gì?
Một số nguyên tố là một số tự nhiên lớn hơn (đôi khi bao gồm một số nguyên dương là 0 trong một số định nghĩa) và không thể được nhân bởi hai số nhỏ hơn. Một ví dụ về số nguyên tố là 7, vì nó chỉ có thể được hình thành bằng cách nhân số 1 và 7. Các ví dụ khác bao gồm 2, 3, 5, 11 và vân vân.
một số có thể được tạo thành với hai số tự nhiên lớn hơn 1 được gọi là hợp số. các ví dụ như các số như 4, 6, 9 và vân vân.
vì lý thuyết cơ bản của toán học, số nguyên tố được sử dụng rộng rãi trong lý thuyết số. định lý này cho thấy rằng số tự nhiên lớn hơn 1 hoặc là số nguyên tố, hoặc có thể phân hủy thành sản phẩm của số nguyên tố. như một ví dụ, số 60 có thể được chia thành sản phẩm của số nguyên tố như sau:
60 = 5 × 3 × 2 × 2
như bạn có thể thấy từ các ví dụ trên, không có số tổng hợp trong việc phân tích.
sự phân hủy nguyên tố là gì?
hệ số nguyên tố là sản phẩm của một số nguyên tố. có rất nhiều thuật toán phân tích, một số phức tạp hơn các thuật toán khác.
Phiên tòa:
một cách để tính toán các số nguyên tố là chia. thử và chia là một trong những thuật toán cơ bản hơn, mặc dù nó rất phức tạp. Nó bao gồm kiểm tra mỗi số nguyên bằng cách chia số nguyên được thảo luận cho số nguyên và xác định số nguyên có thể chia đôi số đó bao nhiêu lần. như một ví dụ đơn giản, đây là sự phân hủy của hệ số nguyên tố 820 sử dụng phương pháp chia:
820 ÷ 2 = 410
410 ÷ 2 = 205
vì 205 không còn được chia đôi, hãy kiểm tra số nguyên tiếp theo. 205 không thể chia cho ba. 4 không phải là số nguyên tố. tuy nhiên, nó có thể chia cho 5:
205 ÷ 5 = 41
vì 41 là một số nguyên tố, và đó là kết thúc của phiên tòa. Vì vậy:
820 = 41 × 5 × 2 × 2
sản phẩm có thể được viết là:
820 = 41 × 5 × 22
Đây cơ bản là một phương pháp “bạo lực” để xác định các yếu tố nguyên tố của một số, và mặc dù 820 là một ví dụ đơn giản, nó có thể nhanh chóng trở nên vô cùng phức tạp.
phân dạng số nguyên tố:
Một phương pháp phổ biến khác cho việc phân tách số nguyên là phân tách số nguyên và có thể bao gồm sử dụng cây hệ số. Tạo một cây nhân tố bao gồm các yếu tố phân hủy tổng số thành tổng số cho đến khi tất cả các số đều là số nguyên tố. Trong ví dụ sau đây, bạn định vị hệ số nguyên bằng cách chia 820 cho hệ số nguyên và tiếp tục chia kết quả cho đến khi tất cả các hệ số nguyên. ví dụ sau đây chỉ ra hai cách để tạo một cây nhân số với số 820:
Vì vậy, bạn có thể thấy rằng trong cả hai trường hợp, sự phân hủy của nguyên tố 820 là:
820 = 41 × 5 × 2 × 2
Mặc dù các phương pháp này hoạt động với các con số nhỏ hơn (và có rất nhiều thuật toán khác), nhưng không có thuật toán nào được biết đến cho các con số lớn hơn nhiều, và thậm chí máy tính có thể mất một thời gian dài để phân tích các số nguyên tố; Vào năm 2009, các nhà khoa học đã hoàn thành một dự án mất 2 năm để sử dụng hàng trăm máy để phân hủy số RSA-768 có 232 chữ số.
