Đề bài
Có những tam thức bậc hai rất giỏi sinh ra số nguyên tố. Chẳng hạn n² + n + 41 cho số nguyên tố với mọi n từ 0 đến 39. Với các số nguyên a và b thỏa mãn |a| ≤ limit và |b| ≤ limit, hãy đếm xem có bao nhiêu giá trị liên tiếp n = 0, 1, 2, ... làm cho n² + an + b là số nguyên tố, dừng lại ở giá trị đầu tiên không cho số nguyên tố. Tìm cặp (a, b) cho chuỗi dài nhất.
Hãy viết quadratic_primes(limit).
Đầu vào
limit: Cận cho giá trị tuyệt đối của a và b.
Đầu ra
Trả về [a, b, run], trong đó run là số số nguyên tố trong chuỗi dài nhất. Nếu nhiều cặp bằng nhau, chọn a nhỏ nhất, rồi đến b nhỏ nhất. Các số nhỏ hơn 2 không phải số nguyên tố, nên cặp nào có giá trị tại n = 0 không nguyên tố thì chuỗi dài 0.
Ràng buộc
0 ≤ limit ≤ 300
Ví dụ
Đầu vào:
limit = 3
Kết quả mong đợi:
expected = [-2, 3, 3]
Đầu vào:
long long limit = 3;
Kết quả mong đợi:
std::vector<long long> expected = {-2, 3, 3};
Đầu vào:
long limit = 3;
Kết quả mong đợi:
long[] expected = new long[] {-2, 3, 3};
Giải thích
Với a = −2 và b = 3, các giá trị tại n = 0, 1, 2, 3 là 3, 2, 3, 6: ba số nguyên tố. Không cặp nào cho chuỗi dài hơn, cũng không có cặp nào với a nhỏ hơn cho chuỗi dài bằng, nên đáp án là [-2, 3, 3].
Đầu vào:
limit = 1
Kết quả mong đợi:
expected = [-1, -1, 0]
Đầu vào:
long long limit = 1;
Kết quả mong đợi:
std::vector<long long> expected = {-1, -1, 0};
Đầu vào:
long limit = 1;
Kết quả mong đợi:
long[] expected = new long[] {-1, -1, 0};
Giải thích
b chỉ có thể là −1, 0 hoặc 1 và không số nào là số nguyên tố, nên mọi chuỗi đều dài 0 và cặp nhỏ nhất thắng: [-1, -1, 0].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tại n = 0 giá trị là b, nên b phải là số nguyên tố thì mới có chuỗi.
Gợi ý 2
Tăng n cho đến khi giá trị không còn là số nguyên tố; giá trị âm và giá trị nhỏ hơn 2 đều kết thúc chuỗi.
Gợi ý 3
Duyệt a và b theo thứ tự tăng dần, và chỉ thay kết quả tốt nhất khi chuỗi dài hơn hẳn.
Độ phức tạp mong đợi
thời gian O(limit² × run × √V), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.