30/09/2018, 23:15
Hỏi thuật toán tốt hơn cho một bài tập C++
Đề bài: Viết chương trình liệt kê các số nguyên có 7 chữ số thoả mãn:
- Là số nguyên tố
- Tổng các chữ số của số đó là một số nguyên tố
- Các chữ số từ trái qua phải tạo thành dãy không giảm
Không biết có hướng giải quyết nào khác giúp bài này chạy nhanh hơn không, chứ code mình viết chạy tính bằng phút
bool kiemTraNguyenTo(int n)
{
if ( (n < 2) || (n % 2 == 0 && n != 2) )
{
return false;
}
for (int i = 3; i < n; i += 2)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
bool kiemTraTongCacSoLaSoNguyenTo(int n)
{
int iSum = 0;
while (n != 0)
{
iSum += n % 10;
n /= 10;
}
return kiemTraNguyenTo(iSum) ? true : false;
}
bool kiemTraTangDan(int n)
{
int k = 10;
while (n != 0)
{
if (n % 10 > k)
{
return false;
}
k = n % 10;
n /= 10;
}
return true;
}
int main()
{
for (int i = 1111111; i < 100000000; i += 2)
{
if ( !kiemTraNguyenTo(i) )
{
continue;
}
if ( !kiemTraTongCacSoLaSoNguyenTo(i) )
{
continue;
}
if ( kiemTraTangDan(i) )
{
printf("
%d", i);
}
}
return 0;
}
Bài liên quan
thay đổi thứ tự các cái if của main đi thì sẽ nhanh hơn, để cái nguyên tố cuối cùng ý
Đầu tiên check tăng dần trước đã đúng thì check tổng là số nguyên tố rồi sau đó check số nguyên tố
Mình làm thế này:
7 chữ số -> 9*7 = 63
Vậy tổng các số nguyên tổ chỉ từ 2 -> 63 (18 số)
-> Phân tích tất cả các số nguyên tố trong đoạn trên thành tổng các số.
Các chữ số ko giảm nên chỉ phân tích những số nguyên tố trên thành tổng của 7 chữ số. (Vì nếu nhỏ hơn 7 chữ số phải chèm số 0 vào giữa -> mất đi tính ko giảm)
Vậy với mỗi 7 chữ số phân tích, ta sắp xếp và kiểm tra tính chẵn lẻ.
Nếu chẵn thì phân tích tiếp, còn lẻ thì ghép lại và kiểm tra số nguyên tố.
Và kiểm tra bằng hàm trên thì ok roài!
Dùng thuật kt snt cơ bản với DPT O(Sqrt(n)) nữa là ngon cơm.~> Vậy bây giờ tối ưu cái phân tích thành tổng nữa là OK.
7 vòng for mà chạy ì xèo luôn :))
Ideone.com
Ideone.com
Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.
Check tổng là SNT trước, rồi check là SNT
Mún chạy nhanh hơn thì giảm số vòng lặp. Cho i chạy tới căn bậc 2 của n là đủ rồi … tương đương n/2 + 1.
Ố chết :))
Mình tưởng thớt dùng thuật căn(n)
sorry sorry.
Để chạy nhanh hơn thì việc tối ưu ở điều kiện nào là khá quan trọng. Giả sử trong đoạn 10^6-> 10^7 là n
Khi sinh dc số ở dk3. Ta có thể kiểm tra ngay ở dk 2 rất nhanh bằng cách xây dựng mảng hằng [0-64] để kiểm tra tổng các chữ số có là snt hay không.
Đến đây bạn sẽ có cỡ vài ngàn số thoã mãn dk 3 và 2. Thuật toán kiểm tra số nguyên tố chỉ cần chạy đến căn là có thể giải quyết gọn gàng dk 1. Đến đây ta có thể hoàn thành bài toán trong 1s là khả thi
Code tham khảo [python] http://ideone.com/9f56n3
9*7=56
Biết nhầm nên sửa rồi mà
Bạn thử đoạn mã này đi
http://pastebin.com/xMBPA4Kx
Cái điều kiện trong if main của thớt nó là i<10^8 là nó thành tới 9 chữ số lận. Với cái thứ hai là sao lại bắt đầu từ i=1111111? Trong khi số bé nhất 7 chữ số là 10^6 mà
Dễ thấy từ 11111111 trở lại về 10000000 là không tăng dần rồi nên bỏ trước luôn cũng được mà bạn
Code viết lại tượng trưng thôi bạn nên không để ý mấy số đó lắm
Thực ra phần trả lời remove của bạn trả lời đúng r đấy
Vì đề kêu dãy các chữ số trong số không giảm nên bắt đầu từ 1111111.
Do các số nhỏ hơn số này có số 0 ở giữa nên tạo thành 1 dãy giãm.
Tưởng remove là không thấy được
24h sau mới không thấy được nhé.
Sao kết quả của bạn không tuần tự từ nhỏ đến lớn vậy. Mình làm theo bài thớt nhưng chỉ cho chạy từ 1111111 tới 9999999 và đổi thứ tự kiểm tra :kt số tăng -> kt tổng các chữ số là snt -> số nguyên tố. KQ chạy 25s.
Hàm int p(int p) sẽ sinh các số có 7 chữ số tăng dần và thoã mãn tổng các chữ số = p. Nên việc này sẽ làm thứ tự xuất hiện kết quả không theo sắp xếp. Nó có thể chạy lâu hơn một chút do 7 vòng for kia phải lặp lại 16 lần.
Có vài trăm số làm cái mảng hằng rồi xuất ra thôi, nghĩ nhiều chi cho mệt
cho 7 vòng for lồng nhau (ứng với 7 chử số) và đảm bảo khi hợp lại nó không giảm
sau đó kiểm tra tổng 7 số có ntố không, nếu có thì mới kiểm tra số đólcó là số nguyên tố không.
Bạn tham khao thêm thuật toán kiểm tra số nguyên số