Cây phân tích thừa số nguyên tố

Phân tích thừa số nguyên tố là phân tách một số nguyên thành các số nguyên tố nhân với nhau tạo ra nó — phép phân tách duy nhất mà mọi hợp số đều có, và chỉ có một mà thôi. Công cụ này nhận số nguyên từ 2 trở lên và phân tích thực sự, sau đó vẽ kết quả thành cây thừa số phân nhánh như trong trường học: bắt đầu từ số ban đầu, tách ra ước số nguyên tố nhỏ nhất, và tiếp tục tách phần còn lại cho đến khi chỉ còn các số nguyên tố.

Quy tắc tách là phép chia thử bởi số nguyên tố nhỏ nhất khả dĩ ở mỗi bước: thử 2 trước, rồi đến các số lẻ 3, 5, 7, 9… cho đến căn bậc hai của giá trị hiện tại. Với 360, quá trình diễn ra là 360 = 2 × 180, rồi 180 = 2 × 90, rồi 90 = 2 × 45, rồi 45 = 5 × 9, rồi 9 = 3 × 3 — năm lần tách kết thúc với sáu lá nguyên tố (2, 2, 2, 3, 3, 5). Gộp nhóm những lá này cho ra dạng lũy thừa rút gọn hiển thị bên dưới sơ đồ: 360 = 2³ × 3² × 5.

Tất cả thao tác này chạy bằng số học BigInt chính xác, vì vậy không bao giờ có sai số làm tròn dấu phẩy động trong quá trình xử lý. Phép chia thử đến căn bậc hai thì nhanh với những số thông thường, nhưng sẽ chậm dần khi ước số nguyên tố nhỏ nhất của đầu vào càng lớn, nên công cụ giới hạn đầu vào ở mức 1.000.000.000.000 (10^12) và hiển thị thông báo rõ ràng khi vượt quá thay vì làm treo trình duyệt — một trình duyệt không có lý do gì phải đơ vì một số nửa nguyên tố khổng lồ chỉ để chứng minh điều gì đó.

Cây thừa số trực quan là cách chuẩn để dạy phân tích thừa số nguyên tố ở trường, và nó vẫn hữu ích sau khi rời ghế nhà trường: rút gọn phân số, tìm ước chung lớn nhất hay bội chung nhỏ nhất bằng cách so sánh số mũ của các thừa số nguyên tố, đơn giản hóa căn bậc hai, và kiểm tra nhanh xem một số có phải là nguyên tố không — tất cả đều quay về cùng một phép phân tách này. Mọi thứ chạy cục bộ trong trình duyệt của bạn — không đăng ký, không vòng gửi về máy chủ.