01/10/2018, 08:15

Kiểm tra nguyên tố lớn!

Em đã biết được nhiều cách kiểm tra số nguyên tố nhưng vẫn chưa giải được các số lớn như tầm trên 50 chữ số ạ, em cần mọi người góp ý ạ!

Nguyễn Duy Hùng viết 10:17 ngày 01/10/2018

Với C++ thì bạn phải xây dung một lớp BigInteger có các phương thức cần thiết như trong số nguyên như cộng trừ nhân chia. Rồi kiểm tra bằng thuật toán như bình thường. Hoặc cũng có thể include thư viện bên thứ 3 xây dựng sẵn để xử lý số nguyên lớn. Còn trong C# hay Java, đặc biệt là Python nó đã có các API xử lý số nguyên lớn luôn rồi nên không phải lo nữa

Trần Hoàn viết 10:21 ngày 01/10/2018

Nguyên tắc tính toán số nguyên lớn thông thường là nhập các string (hay là char[]), mỗi char là một chữ số, rồi tính toán tương tự như con người đặt bút tính từng hàng từ đơn vị, chục, trăm… tính lên, nhớ mấy hạ mấy ấy.

Bạn viết hàm tính số nguyên lớn với đầu vào là 2 string chữ số, return cũng là string chữ số, rồi dùng phép nhân đó để kiểm tra tính nguyên tố

rogp10 viết 10:21 ngày 01/10/2018

Số nguyên tố lớn thì đúng là đầu tiên bạn phải có thư viện bignum đã.

Sau đó bạn quay vài chục vòng Rabin-Miller là có thể khẳng định được.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Phúc

0 chủ đề

0 bài viết

Tác giả nổi bật