Xác định tất cả các cách phân tích N thành tổng của 4 số nguyên tố

Tan_Le · February 28, 2022, 7:32am

Bài tập khó bác nào cùng vào xẻ chơi :))

Cho số nguyên dương N lớn hơn hoặc bằng 8. Hãy phân tích N thành tổng của 4 số nguyên tố, các cách phân tích là hoán vị của nhau được xem là một.

Yêu cầu : Xác định tất cả các cách phân tích N như trên.
Dữ liệu vào : Từ tập tin văn bản PHANTICH.INP. Gồm 1 dòng duy nhất chứa số nguyên dương N
Dữ liệu ra : Ghi ra tập tin văn bản PHANTICH.OUT Gồm M + 1 dòng . Trong đó :
- Dòng đầu tiên là số nguyên dương M : M là số cách phân tích N thành tổng của 4 số nguyên tố.
- M dòng tiếp theo là các kết quả phân tích số N thành tổng 4 số nguyên tố.

Ví dụ :

Dưới đây là code của mình viết nhưng mà hình như bị lỗi chỗ nào ấy

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int main ()
{
	int N, M, i, j, o, p,CheckSNT, X, X2, Tong;
	int Sohang[4], SoNguyenTo[X];
	X = 2;	M = 0;
	Tong = 0;
	ifstream PhanTich ("phantich.txt");
	if(! PhanTich.is_open())
	{
		cout << "Khong tim thay file \n ...";
		return 0;
	}
	PhanTich >> N;
	PhanTich.close();
	cout << "Da doc du lieu \n";
	ofstream PhanTich2 ("ketqua.txt");
	PhanTich2 << "Ket qua : \n";
	SoNguyenTo[1] = 2;
	SoNguyenTo[2] = 3;
	for (int i = 2; i <= N; i++)
	{
		
		for(int j = 2; j <= sqrt((float)i); j++)
	 	{	
			if(i%j == 0)
			{
				CheckSNT = 1;
				break;
			}
			else
			{
				CheckSNT = 2;
			}
		}
		if(CheckSNT != 1)
		{
			X++;
			SoNguyenTo[X] = i;
			
		}
	}
	for ( int i = 1; i <= X; i++)
	{
		cout << SoNguyenTo[i] << endl;
	}
	
	// TH 1 : 4 so giong nhau
	for(int i = 1; i <= X; i++)
	{
		Sohang[1] = SoNguyenTo[i];
		Sohang[2] = SoNguyenTo[i];
		Sohang[3] = SoNguyenTo[i];
		Sohang[4] = SoNguyenTo[i];
		Tong = Sohang[1] + Sohang[2] + Sohang[3] + Sohang[4];
		if(Tong == N)
		{
			M++;
			PhanTich2 << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
			cout << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
			
		}
	}
	// TH 2 : 3 so giong nhau 1 so khac
	for(int i = 1; i <= X; i++)
	{
		Sohang[1] = SoNguyenTo[i];
		Sohang[2] = SoNguyenTo[i];
		Sohang[3] = SoNguyenTo[i];
		for (int j = 1; j <= X; j++)
		{
			Sohang[4] = SoNguyenTo[j];
			Tong = Sohang[1] + Sohang[2] + Sohang[3] + Sohang[4];
			if(Tong == N)
			{
				M++;
				PhanTich2 << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
				cout << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
				
			}
		}
	}
	// TH 3 : 2 so giong nhau 1 va 2 so giong nhau 2
	for(int i = 1; i <= X; i++)
	{
		Sohang[1] = SoNguyenTo[i];
		Sohang[2] = SoNguyenTo[i];	
		for (int j = 2; j <= X; j++)
		{
			Sohang[3] = SoNguyenTo[j];
			Sohang[4] = SoNguyenTo[j];
			Tong = Sohang[1] + Sohang[2] + Sohang[3] + Sohang[4];
			if(Tong == N)
			{
				M++;
				PhanTich2 << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
				cout << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << "\n";
				break;
			}		
		}
	}
	// TH 4 : 2 so giong nhau  
	for(int i = 1; i <= X; i++)
	{
		
		Sohang[1] = SoNguyenTo[i];
		Sohang[1] = SoNguyenTo[i];		
		for (int j = 1 + i; j <= X; j++)
		{
			Sohang[3] = SoNguyenTo[j];
			for (int o = 1 + j; o <= X; o++)
			{
				Sohang[4] = SoNguyenTo[o];
				Tong = Sohang[1] + Sohang[2] + Sohang[3] + Sohang[4];
				if(Tong == N)
				{
					M++;
					PhanTich2 << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
					cout << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
					break;
				}	
			}
				
		}
	}
	// TH  : 4 so khac nhau
	for(int i = 1; i <= X; i++)
	{
		Sohang[1] = SoNguyenTo[i];
		for (int p = 1 + i; p <= X; p++ )
		{
			Sohang[2] = SoNguyenTo[p];		
			for (int j = 1 + p; j <= X; j++)
			{
				Sohang[3] = SoNguyenTo[j];
				for(int o = 1 + j; o <= X; o++)
				{
					Sohang[4] = SoNguyenTo[o];
					Tong = Sohang[1] + Sohang[2] + Sohang[3] + Sohang[4];
					if(Tong == N)
					{
						M++;
						PhanTich2 << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
						cout << N << " = " << Sohang[1] << " + " << Sohang[2] << " + " << Sohang[3] << " + " << Sohang[4] << endl;
						break;
					}
				}
			
			}
		}		
	}
	PhanTich2 << M << endl;
	PhanTich2.close();
	cout << " \n Hoan Tat \n";
	system("pause");
}

htwap · April 2, 2016, 2:33pm

cho code vào markdown đi bạn.

Bài này dễ í mà, Không làm.

Tan_Le · April 2, 2016, 2:34pm

cho vào sao đây mò nãy h

htwap · April 2, 2016, 2:35pm

hình như cho vào được rồi kìa
mà mất mấy cái include thư viện rồi thì phải

Tan_Le · April 2, 2016, 2:37pm

yub dc oy` :)) ! Bài này làm từ trưa tới h không ra … search google tham khảo ko có :(( !!! Đau khổ … chưa tắm chưa nhai cơm nữa chứ hjx

htwap · April 2, 2016, 2:45pm

chắc là bài này dùng đệ quy quay lui, với mỗi cấu hình thì phần tử sau lớn hơn hoặc bằng phần tử trước.

mà hình như dùng đệ quy là cách không tối ưu đâu. chờ @Gio vào xem thế nào

Tan_Le · April 2, 2016, 2:47pm

ùm mình chỉ ms học C++ có 1 tuần à chưa tìm hiểu đệ quy hay quay lui là j nữa để chút xem list tut của a Đạt xem có hem :3

Ta_Ta_Goo · April 2, 2016, 3:26pm

Bài này ngoài phương pháp duyệt trâu bò thì không biết có cách nào tốt hơn không nhỉ.

Gio · April 2, 2016, 4:21pm

Dùng sàng nguyên tố duyệt đến n dc cỡ n/logn số nguyên tố. Dpt nloglogn
Duyet 1cặp: lưu tổng từng cặp thì có (n/logn)^2 cặp. Sort tổng các cặp lập dc
Duyệt 1 cặp còn lại: sau đó dùng tìm nhị phân để kiếm trong mảng 1 cặp phù hợp
Dpt của thuật toán cỡ n^2logn

Code tham khảo: python

htwap · April 2, 2016, 3:53pm

lần này thì gió nói khó hiểu quá, không nắm kịp rồi

Tuan_Tran_Duong · April 2, 2016, 4:36pm

Nhìn code thấy khủng khiếp luôn.

Tong_Cong_Minh · April 2, 2016, 4:38pm

bài này làm mình liên tưởng đến giả thiết goldbach mà tới giờ chỉ có terence tao cmt với n=5 còn nhỏ hơn thì chịu

gannham · April 2, 2016, 5:07pm

chú học gì mà có bài toán chất thế ??? anh có tài liệu giải thuật nâng cao đây , chú cần ko anh share cho

Tan_Le · April 2, 2016, 5:36pm

zạ cần :)) !! E ms học 11 thôi nên toàn học rừng chứ ko có bài bản :((

Tan_Le · April 2, 2016, 5:37pm

Gony · April 2, 2016, 6:00pm

Bậy, chê bạn ấy vậy là không được. Bạn ấy không hiểu thì giúp bạn ấy hiểu vấn đề chứ.

Chú ý nha bạn, không được sử dụng ngôn ngữ teen. Lần sau rút kinh nghiệm nhé.

drgnz · April 2, 2016, 6:16pm

Thế này
1/ Sàng ra 1 danh sách số nguyên tố và bỏ nó vô 1 list riêng. (ở code trên là p )
2/ Tính tổng từng cặp số nguyên tố và lưu lại các cặp đó với tổng của nó. Sau đó sort theo tổng.
3/ Với mỗi cặp đã có, ta tìm cặp còn lại và lôi 2 cặp nguyên tố kia ra là xong.

gannham · April 2, 2016, 8:13pm

dua cai email chu day

tntxtnt · April 2, 2016, 8:20pm

đề ko cho biết N tối đa là bao nhiêu à?

htwap · April 2, 2016, 9:02pm

ý chủ thớt là bảo trình của chủ thớt còn kém, không hiểu Gio viết gì luôn mà