Gợi ý bài tập minh hoạ định lý Bertrand - Chebyshev

[Truong_Dang (Trường Đặng)]

Mình ko biết làm bài tập này mong mọi người gợi ý :<

[rogp10]

Từ 2n-1 chạy xuống

Vẫn là chia thử đến sqrt().

[HR16 (Gà Coder)]

Thêm chỉ xét số lẻ nhanh hơn chút
P/s: Vip pro nhất là dùng Rabin-Miller

[nguyenchiemminhvu (NCMV)]

Mình hay dùng Prime table để kiểm tra số nguyên tố với Time Complexity là O(n) và Space Complexity cũng là O(n). Cách này chỉ để bạn tham khảo chứ mình không khuyến cáo sử dụng, vì với n lớn thì khá tốn kém bộ nhớ.

int MaxPrime(int from, int to)
{
	int res = 0;
	
	bool * check = new bool[to + 1];
	memset(check, false, to + 1);
	
	for (int i = from + (2 - (from % 2)); i <= to; i += 2)
	{
		check[i] = true;
	}
	
	for (int i = from + (3 - (from % 3)); i <= to; i += 3)
	{
		check[i] = true;
	}
	
	for (int i = from + (5 - (from % 5)); i <= to; i += 5)
	{
		check[i] = true;
	}
	
	for (int i = from + (7 - (from % 7)); i <= to; i += 7)
	{
		check[i] = true;
	}
	
	// remove corner cases
	check[2] = check[3] = check[5] = check[7] = false;
	
	for (int i = to - (to % 2 == 0); i >= from; i -= 2)
	{
		if (check[i] == false)
		{
			res = i;
			break;
		}
	}
	
	delete[] check;
	return res;
}

Testing:

n = 3;
cout << MaxPrime(n, 2 * n) << endl;
n = 6;
cout << MaxPrime(n, 2 * n) << endl;
n = 16;
cout << MaxPrime(n, 2 * n) << endl;
n = 21;
cout << MaxPrime(n, 2 * n) << endl;

Result:

5
11
31
41

(Updated: chỉ xét số lẻ như @HR16 gợi ý)