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

Quadratic Primes

Find the quadratic n² + an + b that gives the longest run of primes from n = 0.

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

  • Test primality by trial division
  • Search a two-parameter space
  • Apply tie-breaking rules

Đề bài

Xem bản dịch

Some quadratics are good at making primes. n² + n + 41 gives primes for n = 0 to 39. For whole numbers a and b with |a| ≤ limit and |b| ≤ limit, count how many consecutive values n = 0, 1, 2, ... make n² + an + b prime, stopping at the first value that is not prime. Find the pair with the longest run.

Implement quadratic_primes(limit).

Input

limit: The bound on the absolute values of a and b.

Output

Return [a, b, run], where run is the number of primes in the longest run. If several pairs tie, take the smallest a, then the smallest b. Numbers below 2 are not prime, so a pair whose value at n = 0 is not prime has a run of 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

With a = −2 and b = 3 the values for n = 0, 1, 2, 3 are 3, 2, 3, 6: three primes. No pair does better and no smaller a ties, so the answer is [-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 is −1, 0 or 1 and none of them is prime, so every run is 0 and the smallest pair wins: [-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

At n = 0 the value is b, so b must be prime for any run at all.

Gợi ý 2

Count n upward until the value is not prime; negative values and values below 2 end the run.

Gợi ý 3

Loop a and b in increasing order and replace the best only on a strictly longer run.

Độ phức tạp mong đợi

O(limit² × run × √V) time, O(1) extra space

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.