Bài toán xác định số nguyên tố

#1

Đề bài: xác định một số nguyên dương có n chữ số có phải là số nguyên tố không? n từ 30 đến 100.
Vấn đề của bài toán này mà mình gặp phải đó chính là yêu cầu về thời gian chạy (dưới 5s) và kiểu dữ liệu lưu trữ.
Về thời gian chúng ta có thể bỏ qua, giờ chúng ta bàn về thuật toán.
Để lưu trữ cái số khổng lồ đó mình dùng mảng.
Mình tìm ra được dạng chung của số nguyên tố là 6k + 1 và 6k + 5.
Mình tính dùng loại trừ, nhưng phạm vi rộng quá nên không thể.
Giờ thì tới đây mình bí vì thao tác trên chuỗi số khó quá và cũng chưa tìm được giải thuật nào.
Anh chị em bà con cô bác ai có ý gì hay cho mình xin lãnh giáo ạ!!!

#2

Dùng cái này chạy thử xem có dưới 5s không?

Theo Đạt nhớ đây là quy tắc suy ra một chiều, không thể dùng nó để tìm số nguyên tố được.

1 Like
#3

Bạn có thể dùng Sàng Eratos. Khi mình học thầy cũng yêu cầu bài toán này. Mình thử nhiều thuật toán và có tham khảo đc thuật sàng, thời gian tìm kiếm nhanh hơn những thuật toán mình từng biết.

Input: một số nguyên n > 1
Cho A là một mảng boolean, được đánh số từ 2 đến n,
khởi tạo bằng cách gán tất cả phần tử trong mảng là true.

for i = 2, 3, 4,…, √n:
if A[i] is true:
for j = i2, i2+i, i2+2i,…, n:
A[j]:= false

Lúc này, tất cả i ví dụ như của A[i] nếu true đều là số nguyên tố.

Đọc wiki để biết thêm.

3 Likes
#4

Thực ra có nhiều giải pháp cho bài toán này, nhưng nếu mình chỉ dừng ở mức học tập thì giải pháp của @Is2IT là hợp lý rồi.

Vì dụ ở trên cũng sử dụng cách này. Cách này không phải là rất nhanh, chỉ là nhanh vừa vừa thôi. Nhưng nó đơn giản, dễ thực hiện.

2 Likes
#5

cám ơn bạn, nhưng sàng Eratosthenes là thuật toán để tìm các số nguyên tố nhỏ hơn 100, yêu cầu đề của mình là 1 số nguyên có n chữ số, mà n từ 30 đến 100.
VD: 123453784756748958756475869484756457584746 có phải là số nguyên tố không?
mình không biết dùng kiểu dữ liệu nào cho thằng này cả, nó khủng quá.
thật ra mình dùng chuỗi số lưu trữ nó, nhưng thao tác chuỗi số quá khó, rườm rà, lại vi phạm yêu cầu thời gian. nên mình vẫn còn đang bí lù

#6

Vậy là kiểm tra chuỗi số có 100 ký tự là số có phải là nguyên tố hay không
Nhưng mình không nghĩ ra cách viết code thế nào cho đúng. Nghiên cứu đã :blush:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?