PrimePolynom

SRM 259 · 2005-08-22 · by Andrew_Lazarev

SRM 259 · 2005-08-22 · by Andrew_Lazarev · Brute Force

Show categories

Class Name: PrimePolynom

Return Type: int

Method Name: reveal

Arg Types: (int, int, int)

Problem Statement

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, ...

It is known that no non-constant polynomial function P(n) exists that evaluates to a prime number for all integers n. But there are some famous quadratic polynomials that are prime for all non-negative integers less than M (M depends on the polynomial).

You will be given ints A, B and C. Your method should return the smallest non-negative integer M such that A*M² + B*M + C is not a prime number.

Constraints

A will be between 1 and 10000, inclusive.
B will be between -10000 and 10000, inclusive.
C will be between -10000 and 10000, inclusive.

Examples

1
-1
41
Returns: 41

This is one of the famous polynomials.

1
1
41
Returns: 40

1
1
-13
Returns: 0

No negative numbers are prime.

1
-15
97
Returns: 48

1
-3
43
Returns: 42

82)

1
-79
1601
Returns: 80

The largest possible answer.

Submissions are judged against all 128 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PrimePolynom with a public method int reveal(int A, int B, int C) · 128 test cases · 2 s / 256 MB per case