8
Một cách là tính gcd của mình và kiểm tra xem nó có phải là 1.Cách nhanh nhất để kiểm tra xem hai số được cho là đồng thời không?
Có cách nào nhanh hơn không?
A
Trả lời
12
Thuật toán Euclide (tính gcd) rất nhanh. Khi hai số được rút ngẫu nhiên đồng nhất từ [1, n], số bước trung bình để tính gcd là O(log n). Thời gian tính toán trung bình cần thiết cho mỗi bước là bậc hai theo số chữ số.
Có các lựa chọn thay thế hoạt động tốt hơn một chút (nghĩa là, mỗi bước là tùy ý về số lượng chữ số), nhưng chúng chỉ hiệu quả trên các số nguyên rất lớn. Xem, ví dụ: On Schönhage's algorithm and subquadratic integer gcd computation.
7
nếu bạn đang chạy trên một máy có phân chia/phần còn lại đắt hơn đáng kể so với ca làm việc, hãy xem xét binary GCD.
Các vấn đề liên quan
- 1. cách nhanh chóng để kiểm tra xem một chuỗi ký tự không phải là số
- 2. Cách nhanh nhất để kiểm tra các chữ số trùng lặp của một số là gì?
- 3. Cách nhanh nhất để kiểm tra xem tất cả các giá trị trong một mảng có phải là số không?
- 4. Cách nhanh nhất để thực hiện thêm số nguyên không được kiểm tra trong VB.Net?
- 5. Cách nhanh nhất để kiểm tra xem chuỗi có thể được phân tích cú pháp
- 6. Cách nhanh nhất để kiểm tra xem một loại có bị blittable không?
- 7. Java - Cách nhanh nhất để kiểm tra xem URL có tồn tại không?
- 8. MySQL - Cách nhanh nhất để kiểm tra xem dữ liệu trong bảng InnoDB đã thay đổi
- 9. Cách tốt nhất để kiểm tra đơn vị một phương pháp không đồng bộ là gì?
- 10. Cách dễ nhất để kiểm tra số
- 11. Làm cách nào để kiểm tra xem thông số mẫu có phải là một tham số của hai không?
- 12. Cách nhanh nhất để thực hiện yêu cầu web đồng thời trong Perl là gì?
- 13. Có cách nào nhanh chóng để kiểm tra xem cột BẤT CỨ là NULL không?
- 14. Cách kiểm tra xem JCheckBox có được kiểm tra không?
- 15. HashMap đồng thời: kiểm tra kích thước
- 16. Làm cách nào để kiểm tra xem số có chia hết cho một số nhất định không?
- 17. Cách kiểm tra mã không đồng bộ
- 18. Kiểm tra tải cho 1000 người dùng đồng thời
- 19. Cách nhanh nhất để kiểm tra xem một số bản ghi trong bảng cơ sở dữ liệu?
- 20. mã ngắn nhất để kiểm tra xem một số là trong một phạm vi trong JavaScript
- 21. Cách tốt nhất và nhanh nhất để kiểm tra xem hình ảnh có hợp lệ trong PHP không?
- 22. Để kiểm tra xem hai tệp hình ảnh có giống nhau không. Kiểm tra hoặc băm?
- 23. Cách tốt nhất để kiểm tra xem cặp đôi có phải là số nguyên trong C# không?
- 24. Cách tốt nhất để kiểm tra xem một danh sách không phải là null?
- 25. C cách nhanh hơn để kiểm tra xem thư mục có tồn tại không
- 26. Golang - Kiểm tra số lượng đối số? Đồng thời Nhập Người dùng - Kiểm tra mục nhập trở về (dòng trống) ""
- 27. Cách tốt nhất để kiểm tra tệp để xem tệp zip của nó là gì?
- 28. Cách tốt nhất để kiểm tra xem Biến có phải là không?
- 29. Cách để nhanh chóng kiểm tra xem chuỗi là XML hay JSON trong C#
- 30. Cách ngắn nhất để kiểm tra xem biến có chứa số nguyên dương bằng PHP không?
Tôi muốn nhận xét rằng hơi thô sơ để đo độ phức tạp của thuật toán số học mà không tính đến chi phí của các phép tính số học. –
Số bước xấu nhất là O (log n), khi hai số là các mục liên tiếp trong dãy Fibonacci. –
@Pavel Shved: Tôi đã xem xét chi phí. cf. câu "Thời gian tính toán trung bình cần thiết cho mỗi bước là bậc hai trong số chữ số." – jason