1.

import java.util.Scanner;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 960 Gaussian Primes
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=901
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.128
*/

public class Main {

// Works only for positive numbers bigger than 0
private static boolean isPrime(int x) {
// Manually test for 1, 2 and 3
if (x <= 3) return true;
// Sort out divisible by 2 and 3
if (x % 2 == 0) return false;
if (x % 3 == 0) return false;
// We don't need to test for divisibles of 2 and 3
// So we just need to increment our divisor by 2 and 4 (alternating)
int divisor = 5; // We start at 5
int increment = 2;
int maxDivisor = (int) Math.round(Math.sqrt(x));

while (divisor <= maxDivisor) {
if (x % divisor == 0) return false;
divisor += increment;
increment = 6 - increment; // Alternate between 2 and 4
}

return true;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int testCases = sc.nextInt();
int re, im;
int reSqrPlusImSqr;

for (int tc = 0; tc < testCases; tc++) {
re = sc.nextInt();
im = sc.nextInt();

if (re == 0) {
if ((Math.abs(im) % 4) == 3) {
if (isPrime(Math.abs(im))) {
System.out.println("P");
} else {
System.out.println("C");
}
} else {
System.out.println("C");
}
} else {
if (im == 0) {
if ((Math.abs(re) % 4) == 3) {
if (isPrime(Math.abs(re))) {
System.out.println("P");
} else {
System.out.println("C");
}
} else {
System.out.println("C");
}
} else {
reSqrPlusImSqr = re*re + im*im;
if (isPrime(reSqrPlusImSqr)) {
System.out.println("P");
} else {
System.out.println("C");
}
}
}
}
}

}


2.

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Brute Force
* Problem: 960 Gaussian Primes
* Accepted: 1.828
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static boolean isPrime(long n)
{
if(n < 2)
return false;

if(n % 2 == 0)
return false;

int squareRoot = (int)Math.sqrt(n);
for(int i = 3; i <= squareRoot; i += 2)
if(n % i == 0)
return false;

return true;
}

private static boolean isGaussianPrime(long a, long b)
{
if(a == 0 && isPrime(Math.abs(b)) && Math.abs(b) % 4 == 3)
return true;

if(b == 0 && isPrime(Math.abs(a)) && Math.abs(a) % 4 == 3)
return true;

if(isPrime(a*a+b*b))
return true;

return false;
}

public static void main(String...args)
{
Scanner sc = new Scanner(System.in);

int testCases = sc.nextInt();
for(int tc = 0; tc < testCases; tc++)
if(isGaussianPrime(sc.nextInt(), sc.nextInt()))
System.out.println("P");
else
System.out.println("C");
}
}