1.


/**
* Angewandte Mathematik, SS11
* Problem: 960 Gaussian Primes
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2113
*
* @author Schramm, Felix
* @author Vogel, Johannes
* @version 1.0, 03/28/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.168
*/

import java.util.*;

public class Main {
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
int samples = scanner.nextInt();
for(int i=0;i<samples;i++){
int real = scanner.nextInt();
int imgnry = scanner.nextInt();
if(isGaussianPrime(real,imgnry))
System.out.println("P");
else
System.out.println("C");
}

}

// vgl. http://www.wolframalpha.com/input/?i=gaussian+prime
private static boolean isGaussianPrime(int real, int imgnry){
if(real==0){
imgnry = Math.abs(imgnry);
return isPrime(imgnry) && imgnry%4==3;
}
else if(imgnry==0){
real = Math.abs(real);
return isPrime(real) && real%4==3;
}
else
return isPrime(real * real + imgnry * imgnry);
}

private static boolean isPrime(int number){
boolean prime = true;
if(number<2)
return false;
if(number==2) return true;
if(number%2==0) return false;
int sqroot = (int)Math.sqrt(number);
for(int i=3;i<=sqroot&&prime;i+=2)
prime=number%i==0?false:true;
return prime;
}
}


2.

package sem2.am.gaussianprimes;

/**
* Angewandte Mathematik, SS11
* Problem: 960 - Gaussian Primes
* Link: http://uva.onlinejudge.org/external/9/960.html
*
* @author Florian Stein
* @author Franz Sommer
* @version 1.0, 03/28/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 2.068
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main

{
public static void main(String args[]) throws Exception {

// Inputhandling
Scanner sc = new Scanner(System.in);

int loops = sc.nextInt() * 2;

int a = 0;
int b = 0;

int[] primes = findPrimes(10000);
Arrays.sort(primes);
// System.out.println(Arrays.toString(primes));
// Outputvariables

// Testing
while (sc.hasNextLine() && loops > 0) {
a = sc.nextInt();
// System.out.println(a);
b = sc.nextInt();
// System.out.println(b);

// System.out.println(Arrays.binarySearch(primes, a*a+b*b ));

// 1st Condition
if (a != 0 && b != 0
&& Arrays.binarySearch(primes, a * a + b * b) >= 0)
System.out.println("P");

// System.out.println(Boolean.toString(a != 0) +
// Boolean.toString(b!=0) +
// Boolean.toString(Arrays.binarySearch(primes, a*a+b*b )>=2));

// 2nd Condition
if (a == 0 && Arrays.binarySearch(primes, Math.abs(b)) > 0
&& (Math.abs(b) % 4) == 3) {
System.out.println("P");
}
// System.out.println(Boolean.toString((a == 0)) +
// Boolean.toString((Arrays.binarySearch(primes,Math.abs(b))>0))
// +((Math.abs(b) % 4) ==3 ) );

// 3rd Condition
if (b == 0 && Arrays.binarySearch(primes, Math.abs(a)) > 0
&& (Math.abs(a) % 4) == 3)
System.out.println("P");
// System.out.println(Boolean.toString(b == 0) +
// Boolean.toString(Arrays.binarySearch(primes,Math.abs(a))>0) +
// Boolean.toString((Math.abs(a) % 4) ==3 ));

if ((!(b == 0 && Arrays.binarySearch(primes, Math.abs(a)) > 0 && (Math
.abs(a) % 4) == 3) && !(a == 0
&& Arrays.binarySearch(primes, Math.abs(b)) > 0 && (Math
.abs(b) % 4) == 3))
&& !(a != 0 && b != 0 && Arrays.binarySearch(primes, a * a
+ b * b) >= 0))
System.out.println("C");
loops = loops - 2;
}

}

public static int[] findPrimes(int x) // finds prime numbers with sieth of
// Erasthotes
{
int list[] = new int[x + 1];
for (int i = 1; i < list.length; i++) {
list[i] = i;
}

// Sieth Algorithm
list[1] = 0;
int setprime = 2;
for (int i = 2; setprime * i <= x; i++) {
list[setprime * i] = 0;
}

while (setprime <= (int) Math.sqrt(x)) {
for (int i = setprime; i <= list.length; i++) {
if (list[i] > setprime) {
setprime = list[i];
break;
}
}

for (int i = 0; (setprime * setprime) + setprime * i < list.length; i++) {
list[(setprime * setprime) + setprime * i] = 0;
}
}

ArrayList<Integer> listTest = new ArrayList<Integer>();
Arrays.sort(list);

for (int j = list.length - 1; list[j] > 0; j--) {
listTest.add(list[j]);
}
// listTest.add(1);

Object[] tmp_array = listTest.toArray();
int finalarray[] = new int[tmp_array.length];
for (int i = 0; i < tmp_array.length; i++) {
finalarray[i] = ((Integer) tmp_array[i]).intValue();
}
return (finalarray);
}

}



-----------------------------------------------------------------------------

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");
}
}