programming language is JAVA: The game of primeNim works as follows: n > 1 stone

Question

programming language is JAVA:

The game of primeNim works as follows: n > 1 stones are placed on a table between two players.. For each person's turn there will be n stones left on the table. If n is a prime number then the current player loses and the other player wins. Otherwise the player removes 1, 2 or 3 stones. (Except if n is 4 the player may remove at most two stones.)

Play continues until one of the players gets stuck with a prime number. Then that player loses and the other player wins.

Implement a method

that returns a winning play (1, 2 or 3) or -1 if there is no winning play.

For example with n = 6 (six stones left) the current player should remove 1 stone in order to leave 5 (a prime number) for her opponent. Removing 3 stones would also work but we'll assume the method always returns the smallest number that ensures a win.

There is a boolean isPrime(int n) method  available for you to call.

You will need one recursive call for each possible number of stones to remove (1, 2 or 3).

When a recursive call returns -1, that means we've found a winning move. Put the appropriate return statement  right after each recursive call to be more efficient.

Here is a table of correct return values up to n = 54.

2 -1
3 -1
4 1
5 -1
6 1
7 -1
8 1
9 2
10 3
11 -1
12 1
13 -1
14 1
15 2
16 3
17 -1
18 1
19 -1
20 1
21 2
22 3
23 -1
24 1
25 2
26 3
27 -1
28 1
29 -1
30 1
31 -1
32 1
33 2
34 3
35 -1
36 1
37 -1
38 1
39 2
40 3
41 -1
42 1
43 -1
44 1
45 2
46 3
47 -1
48 1
49 2
50 3
51 -1
52 1
53 -1
54 1

Explanation / Answer

JAVA PROGRAM :

import java.util.*;

public class Sample1 {

//This method returns if n is prime or not
static boolean isPrime(int n){
//If n is even return false
if(n%2==0){
return false;
}
int e = (int)Math.sqrt(n);
//Check odd numbers from 3 to sqrt(n)
for(int i=3;i<=e;i+=2){
//if n is divisible by i, return false;
if(n%i==0){
return false;
}
}
//Return true otherwise
return true;
}
static int primeNim(int n){   
//If n is prime, return -1
if(isPrime(n)){
return -1;
}
//Call recursively
if(primeNim(n-1)==-1){
return 1;
}
if(primeNim(n-2)==-1){
return 2;
}
if(primeNim(n-3)==-1){
return 3;
}
return -1;
}
  
public static void main(String[] args) {
// System.out.println(primeN(9));
for(int i=2;i<=54;i++){
System.out.println(i+" "+primeNim(i));
}
//
}
}

OUTPUT :

2 1
3 -1
4 1
5 -1
6 1
7 -1
8 1
9 2
10 3
11 -1
12 1
13 -1
14 1
15 2
16 3
17 -1
18 1
19 -1
20 1
21 2
22 3
23 -1
24 1
25 2
26 3
27 -1
28 1
29 -1
30 1
31 -1
32 1
33 2
34 3
35 -1
36 1
37 -1
38 1
39 2
40 3
41 -1
42 1
43 -1
44 1
45 2
46 3
47 -1
48 1
49 2
50 3
51 -1
52 1
53 -1
54 1

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.