Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Tam thức bậc hai sinh số nguyên tố

Tìm tam thức n² + an + b cho chuỗi số nguyên tố liên tiếp dài nhất bắt đầu từ n = 0.

Bạn sẽ học được gì

  • Kiểm tra số nguyên tố bằng phép chia thử
  • Tìm kiếm trên không gian hai tham số
  • Áp dụng quy tắc chọn khi có kết quả bằng nhau

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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].

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.