Vương Như

Để tìm ước của số bất kỳ <= 10^7 thì có một cách đó là tìm các số nguyên tố nhỏ hơn 3163 (~ sqrt(10^7)), sau đó chia lần lượt để tách số ban đầu ra các thừa số nguyên tố.

ví dụ: 140 = 2.2.5.7

sau khi tìm được các số thì nhóm từng số ra sẽ tìm được các ước.

Ước của 140 là: 2, 5, 7, 4, 10, 14, 35, 20, 28, 70, 140.

#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/