TopCoder Statistics - Problem Statement

Problem Statement

A famous probabilistic primality test makes use of Fermat's Little Theorem from number theory. The theorem states

         p-1
	b     %   p  =  1

for all primes p, with b satisfying 1 < b < p, and % denoting modulus or remainder. To refresh your memory, a prime is an integer greater than 1 whose only factors are 1 and itself. In order to test some potential prime q we do the following:

Choose some b-value and compute b^(q-1) % q.
If this value is not 1 then you know q is not prime.
If this value is 1, then you are more sure q is prime than before.

Given q you will try each b-value beginning with 2 until you reach q-1. If at least one of the b-values fails the test stated above (do not produce 1) then return the lowest failing b-value. If all pass return q.

When computing b^(q-1) % q the numbers can get enormous unless certain measures are taken. For one thing, after each multiplication you can apply the modulus. For example,

	190^11 % 300  =  ((190^5 % 300) * (190^6 % 300)) % 300  .

In addition, repeated squaring can speed up the exponentiation process. For example,

	a^9 = a*a*a*a*a*a*a*a*a      requires 8 multiplications but
        a^9 = a*((a^2)^2)^2          requires 4 multiplications.

We can combine the two methods above as illustrated in the following example where we compute a^11 % 12:

	a^11 % 12 = (a * (a^10 % 12)) % 12 
        a^10 % 12 = (a^5 % 12)^2 % 12 
        a^5  % 12 = (a * (a^4 % 12)) % 12 
        a^4  % 12 = (a^2 % 12)^2 % 12 
	a^2  % 12 = (a*a) % 12

Definition

Class:: PseudoPrimeTest
Method:: firstFail
Parameters:: int
Returns:: int
Method signature:: int firstFail(int q)
(be sure your method is public)

Constraints

q will be between 3 and 32000 inclusive.

Examples

3

Returns: 3

Since 2^2 % 3 = 4 % 3 = 1 simply return 3.
1729

Returns: 7

Here we have 2^1728 % 1729 = 1 3^1728 % 1729 = 1 4^1728 % 1729 = 1 5^1728 % 1729 = 1 6^1728 % 1729 = 1 7^1728 % 1729 = 742 so 7 is returned.
5

Returns: 5
561

Returns: 3
7

Returns: 7
341

Returns: 3
561

Returns: 3
645

Returns: 3
1105

Returns: 5
1387

Returns: 3
4

Returns: 2
1905

Returns: 3
2047

Returns: 3
2465

Returns: 5
2701

Returns: 5
2821

Returns: 7
3277

Returns: 3
4033

Returns: 3
4369

Returns: 3
4371

Returns: 3
4681

Returns: 3
5461

Returns: 3
6601

Returns: 7
7957

Returns: 3
8321

Returns: 3
8481

Returns: 3
8911

Returns: 7
10261

Returns: 3
10585

Returns: 5
11305

Returns: 3
12801

Returns: 3
13741

Returns: 3
13747

Returns: 3
13981

Returns: 3
14491

Returns: 3
15709

Returns: 3
15841

Returns: 7
16705

Returns: 3
18705

Returns: 3
18721

Returns: 5
19951

Returns: 3
23001

Returns: 3
23377

Returns: 3
25761

Returns: 3
29341

Returns: 13
30121

Returns: 3
30889

Returns: 3
31417

Returns: 3
31609

Returns: 3
31621

Returns: 5
31859

Returns: 31859
31873

Returns: 31873
31883

Returns: 31883
31891

Returns: 31891
31907

Returns: 31907
31957

Returns: 31957
31963

Returns: 31963
31973

Returns: 31973
31981

Returns: 31981
31991

Returns: 31991
31992

Returns: 2
32000

Returns: 2
11

Returns: 11
12

Returns: 2
13

Returns: 13
14

Returns: 2
15

Returns: 2
16

Returns: 2
17

Returns: 17
18

Returns: 2
19

Returns: 19
31859

Returns: 31859
32000

Returns: 2

Statistics

Problem Statement for "PseudoPrimeTest"

Problem Statement

Definition

Constraints

Examples