Hỏi thuật toán tốt hơn cho một bài tập C++

#1

Đề 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("\n%d", i);
		}
	}

return 0;
}
2 Likes
#2

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 ý

#3

Đầ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ố

1 Like
#4

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 :))

4 Likes
#5

Check tổng là SNT trước, rồi check là SNT

1 Like
#6

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.

3 Likes
#7

Ố chết :))
Mình tưởng thớt dùng thuật căn(n)
sorry sorry.

2 Likes
#8

Để 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

  • dk là số nguyên tố: khá nhiều số cỡ n/logn
  • tổng các chữ số là số nguyên tố: thì tổng các chữ số sẽ là các số nguyên tố nằm trong [7,61] nên việc sinh tất cả số thoã mãn dk này cũng khá nhiều
  • chữ số không giảm: điều kiện chữ số không giảm là điều kiện khá tốt để sinh các số, loại bỏ trường hợp hoán vị ở dk 2. Vì vậy nếu sử dụng phương pháp sinh số thoã mãn dk 3 thì sẽ hạn chế rất nhiều số.
    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
3 Likes
#9

9*7=56 :grin:

3 Likes
#10

:joy: Biết nhầm nên sửa rồi mà

4 Likes
#11

Bạn thử đoạn mã này đi
http://pastebin.com/xMBPA4Kx

#12

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à

#13

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

1 Like
#14

Code viết lại tượng trưng thôi bạn nên không để ý mấy số đó lắm :smiley:

#15

Thực ra phần trả lời remove của bạn trả lời đúng r đấy :stuck_out_tongue:
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.

3 Likes
#16

Tưởng remove là không thấy được :smiley:

1 Like
#17

:wink: 24h sau mới không thấy được nhé.

2 Likes
#19

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.

#20

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.

1 Like
#21

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

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