Vương Như

Đề này đọc quen quen, hình như trước đây từng làm rồi. Tìm các số nguyên tố nhỏ hơn 500. Duyệt từng số trong danh sách đã cho, xong phân tích từng số ra thành tích của các số nguyên tố,

sắp xếp và đếm số lượng các số nguyên tố, sau đó cập nhật các số nguyên tố vào danh sách mới.

Danh sách mới sẽ bao gồm các số nguyên tố và số lần xuất hiện. Nếu bất kỳ số nguyên tố nào có số lượng lớn hơn thì cập nhật lại.

Cuối cùng thì tính tích tất cả các số nguyên tố trong danh sách để tìm ra kết quả.

Ví dụ:

danh sách ban đầu là 120, 230, 15, 28

Tách ra thành tích các số nguyên tố:

120 = 2x2x2x3x5

230 = 2x5x23

15 = 3x5

28 = 2x2x7

Khi duyệt 120, danh sách các số nguyên tố và số lượng tương ứng là:

2: 3, 3: 1, 5: 1

tương tự với 230 thì danh sách được cập nhật là:

2: 3, 3: 1, 5: 1, 23:1

với 15:

2: 3, 3: 1, 5: 1, 23: 1

với 28:

2: 3, 3: 1, 5: 1, 7: 1, 23: 1

Cuối cùng, kết quả phải tìm là:

2x2x2 x 3 x 5 x 7 x 23 = 19320.

#include <time.h>

const int limit = 1e8 + 8;
long long p[limit / 64 + 11];

bool test(int idx) {
	return (p[idx / 64] & (1ULL<<(idx % 63))) == 0;
}

void mark(int idx) {
	p[idx / 64] |= (1ULL<<(idx % 63));
}

void sieve() {
	mark(0);
	mark(1);
	for (int i = 3; i * i < limit; i += 2) {
		if (test(i)) {
			for (long long j = i * i; j < limit; j += i * 2) {
				mark(j);
			}
		}
	}
}

#define ri register int
void sieve2() {
	ri pSize = limit / 64 + 11;
	for(ri i=0; i<pSize; ++i) {
		p[i] = 0;
	}

	register long long* pNum = p;
	for (ri i = 3; i < limit; i+=2) {
		if (*pNum & (1ULL << (i & 0xff)) == 0) {
			for (ri j = i + i; j < limit; j += i) {
				p[j >> 8] |= (1ULL<<(j & 0xff));
			}
		}
		if(i & 0xff == 0) {
			pNum++;
		}
	}
}

int main() {
	clock_t start = clock();
	sieve();
	printf("%ld\n", clock() - start);

	start = clock();
	sieve2();
	printf("%ld\n", clock() - start);

	getchar();
	return 0;
}

• Có thể tối ưu bằng cách sử dụng thanh ghi (register).
• Phép chia cho 64 có thể thay bằng dịch 8 bit sang phải.
• Chia lấy dư cho 64 có thể sử dụng phép và bit với 255 (& 0xff).
• Có thể loại các trường hợp số chia hết cho 2.
• Sử dụng pNum để duyệt từng phần tử của mảng p, tránh mỗi lần lại tìm lại phần tử theo chỉ số.
• Còn việc tính đến sqrt(limit) thì mình không chắc có đúng không, vì nếu chỉ lấy đến sqrt(limit) thì khai báo limit ngay từ đầu được rồi, cần gì làm limit cho thừa.

Đọc lời giải thì mấu chốt không phải cứu tất cả, mà là cứu 99 người phía trước, còn người thứ 100 sẽ chịu hy sinh để nhắc màu cho 99 người còn lại. Nhưng mà liệu có cách nào có thể cứu được tất cả 100 người không nhỉ?

https://www.google.com/search?q=Sự+khác+nhau+giữa+return+pointer+và+return+reference.+Sử+dụng+khi+nào%3FTại+sao%3F

Tìm hiểu : cây nhị phân là gì? biểu thức trung tố là gì? -> cách biểu diễn biểu thức trung tố bằng cây nhị phân -> sử dụng để tính toán, biểu diễn lại biểu thức trung tố sang hậu tố và tiền tố.

1 - Thiếu dấu đóng ngoặc tròn ở dòng đầu tiên

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
	ofstream write("test.txt", ios::binary);

	int a[] = {1, 2, 3, 4, 7, 10}, n;
	write.write(reinterpret_cast<char*> (a), sizeof(a));

	write.close();

	ifstream read("test.txt");

	while(!read.eof())
	{
		n = 88;
		read.read(reinterpret_cast<char*> (&n), 4);
		cout << n;
	}
	/*
	while(read.read(reinterpret_cast<char*> (&n), 4))
	{
		cout << n;
	}

	if(read.eof())
	{
		cout << " end";
	}
	else
	{
		cout << " error";
	}
	*/
	read.close();

    return 0;
}

có vẻ read.eof() dùng để kiểm tra lỗi, nếu set n bằng 88 trước khi đọc thì sẽ thấy câu lệnh đọc cuối cùng không được thực hiện.

Nguồn:

https://cplusplus.com/reference/ios/ios/eof/

https://cplusplus.com/reference/istream/istream/read/