# Check if a number is a Pythagorean Prime or not in Java

## Introduction:

A Pythagorean prime is a prime number of the form 4n + 1, where n is a non-negative integer. These prime numbers have a special property related to Pythagorean triples and are used in various mathematical contexts.

## Approach: Brute Force

The brute force approach involves checking each number individually to determine if it is a Pythagorean Prime. To do this, you iterate through numbers starting from 2 (the smallest prime number) up to the given number and perform two checks:

• Check if the number is prime.
• Check if the number is of the form "4n + 1."

### Algorithm:

Step 1: Initialize a function isPrime(n) to check if a given number n is prime.

Step 1.1: If n is less than or equal to 1, return false (0 and 1 are not prime).

Step 1.2: If n is less than or equal to 3, return true (2 and 3 are prime). If n is divisible by 2 or 3, return false (multiples of 2 and 3 are not prime).

Step 2: Initialize a variable i to 5 (the first number of the form 6k + 1). Repeat the following until i * i is less than or equal to n. If n is divisible by i or n is divisible by i + 2, return false.

Step 3: Increment i by 6 (moving to the next numbers of the form 6k + 1 or 6k + 5). If no divisors are found, return true. Create a function isPythagoreanPrime(n) to check if a number n is a Pythagorean Prime.

Step 4: Call the isPrime function with the input number n to check if it's prime. Check if n is of the form "4n + 1" by verifying if n % 4 == 1.

Step 4.1: Return true if both conditions are met; otherwise, return false.

Step 5: In the main function, initialize an integer variable number with the value you want to check for Pythagorean Prime.

Step 5.1: Call the isPythagoreanPrime(number) function to check if the number is a Pythagorean Prime.

Step 5.2: If it returns true, print that the number is a Pythagorean Prime. If it returns false, print that the number is not a Pythagorean Prime.

Filename: BruteForce.java

```public class BruteForce {

// Function to check if a number is prime

static boolean isPrime(int n) {

if (n <= 1) {

return false; // 0 and 1 are not prime

}

if (n <= 3) {

return true; // 2 and 3 are prime

}

if (n % 2 == 0 || n % 3 == 0) {

return false; // Multiples of 2 and 3 are not prime

}

for (int i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0) {

return false; // Check for divisibility by numbers of the form 6k + 1 or 6k + 5

}

}

return true;

}

// Function to check if a number is a Pythagorean Prime

static boolean isPythagoreanPrime(int n) {

return isPrime(n) && (n % 4 == 1); // Check if the number is prime and of the form "4n + 1"

}

public static void main(String[] args) {

int number = 17; // Replace with the number you want to check

if (isPythagoreanPrime(number)) {

System.out.println(number + " is a Pythagorean Prime.");

} else {

System.out.println(number + " is not a Pythagorean Prime.");

}

}

}```

Output:

`17 is a Pythagorean Prime.    `

Time Complexity:

The isPrime function checks if a number is prime and takes O(sqrt(n)) time because we iterate up to the square root of n. The loop in the isPrime function runs in O(sqrt(n)/6) time since it iterates through numbers of the form "6k ± 1" up to sqrt(n).

Hence, the overall time complexity is O(sqrt(n)).

Space Complexity:

The isPrime function uses a constant amount of space for variables and does not depend on the input, so it has O(1) space complexity. The isPythagoreanPrime function, again, uses a constant amount of space for variables, so it also has O(1) space complexity.

Hence, overall space complexity is O(1).

## Approach: Mathematical Property Approach

The mathematical property approach uses a mathematical property to directly check if a number is a Pythagorean Prime without explicitly checking for primality.

Algorithm:

Step 1: Create a function isPythagoreanPrime(n) to check if a number n is a Pythagorean Prime.

Step 2: Check if n % 4 == 1. If the condition is met (i.e., n is of the form "4n + 1"), return true, indicating that it's a Pythagorean Prime. Otherwise, return false.

Step 3: In the main function, initialize an integer variable number with the value you want to check for being a Pythagorean Prime.

Step 3.1: Call the isPythagoreanPrime(number) function to determine whether the number meets the Pythagorean Prime criteria.

Step 3.2: If it returns true, print that the number is a Pythagorean Prime. If it returns false, print that the number is not a Pythagorean Prime.

Filename: MathematicalPythagoreanPrimeChecker.java

```public class MathematicalPythagoreanPrimeChecker {

// Function to check if a number is a Pythagorean Prime using the mathematical property

static boolean isPythagoreanPrime(int n) {

return (n % 4 == 1); // Check if the number is of the form "4n + 1"

}

public static void main(String[] args) {

int number = 17; // Replace with the number you want to check

if (isPythagoreanPrime(number)) {

System.out.println(number + " is a Pythagorean Prime.");

} else {

System.out.println(number + " is not a Pythagorean Prime.");

}

}

}```

Output:

`17 is a Pythagorean Prime. `

Time Complexity:

The time complexity of this function is O(1) because it performs a simple arithmetic operation (n % 4) and returns the result. The execution time is constant and does not depend on the size of the input number n.

Overall time complexity is O(1).

Space Complexity:

The isPythagoreanPrime function uses a constant amount of memory for variables (n and the result of the modulus operation), so it has O(1) space complexity. The main function also uses a constant amount of memory for variables (number, the result of the function call), so it has O(1) space complexity.

Overall space Complexity is O(1).

## Approach: Sieve of Eratosthenes

In this approach, it involves generating prime numbers using the Sieve of Eratosthenes and then checking if a given number is in the form of "4n + 1" among the list of primes. If the conditions are met, then the input number is a Pythagorean Prime.

Algorithm:

Step 1: Create a function sieveOfEratosthenes(n) to generate a list of prime numbers up to n using the Sieve of Eratosthenes algorithm.

Step 1.1: Initialize a boolean array isPrime of size n + 1 and set all elements to true.

Step 1.2: Set isPrime[0] and isPrime[1] to false since 0 and 1 are not prime.

Step 2: For each integer p from 2 to the square root of n:

Step 2.1: If isPrime[p] is true (indicating p is prime). Mark all multiples of p as false in the isPrime array, starting from p*p up to n, with increments of p.

Step 2.2: Return the isPrime array, where isPrime[i] is true if i is prime; otherwise, it is false.

Step 3: Create a function isPythagoreanPrime(n) to check if a number n is a Pythagorean Prime.

Step 3.1: If n is less than or equal to 1, return false (0 and 1 are not Pythagorean Primes). Generate a list of prime numbers up to n using sieveOfEratosthenes(n).

Step 3.2: Check if n is prime by looking up the corresponding value in the isPrime array. Check if n is of the form "4n + 1" by verifying if n % 4 == 1. If both conditions are met, return true; otherwise, return false.

Step 4: In the main function, initialize an integer variable number with the value you want to check for being a Pythagorean Prime.

Step 4.1: Call the isPythagoreanPrime(number) function to determine whether the number meets the Pythagorean Prime criteria.

Step 4.2: If it returns true, print that the number is a Pythagorean Prime. If it returns false, print that the number is not a Pythagorean Prime.

Filename: SieveOfEratosthenes.java

```import java.util.Arrays;

public class SieveOfEratosthenes {

// Function to generate a list of primes using Sieve of Eratosthenes

static boolean[] sieveOfEratosthenes(int n) {

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true);

isPrime[0] = isPrime[1] = false;

for (int p = 2; p * p <= n; p++) {

if (isPrime[p]) {

for (int i = p * p; i <= n; i += p) {

isPrime[i] = false;

}

}

}

return isPrime;

}

// Function to check if a number is a Pythagorean Prime

static boolean isPythagoreanPrime(int n) {

if (n <= 1) {

return false;

}

boolean[] primes = sieveOfEratosthenes(n);

return primes[n] && (n % 4 == 1);

}

public static void main(String[] args) {

int number = 17; // Replace with the number you want to check

if (isPythagoreanPrime(number)) {

System.out.println(number + " is a Pythagorean Prime.");

} else {

System.out.println(number + " is not a Pythagorean Prime.");

}

}

}```

Output:

`17 is a Pythagorean Prime.  `

Time Complexity:

Generating prime numbers up to n using the Sieve of Eratosthenes takes O(n * log(log(n))) time. This is the dominant factor in the time complexity because it involves iterating through numbers up to n and marking multiples of primes.

Overall time complexity is O(n * log(log(n))).

Space Complexity:

The sieveOfEratosthenes function uses a boolean array of size n + 1 to store prime flags, resulting in O(n) space complexity for the isPrime array. The isPythagoreanPrime function uses a constant amount of memory for variables, so it has O(1) space complexity.

Overall space complexity is O(n).

### Approach: Modified Sieve of Eratosthenes with Pythagorean Prime Check

The "Modified Sieve of Eratosthenes with Pythagorean Prime Check" approach is a technique used to find Pythagorean Primes within a given range of numbers efficiently. It is a modification of the classic Sieve of Eratosthenes algorithm for generating prime numbers. The difference is we are checking if each prime number satisfies the Pythagorean Prime property (i.e., if (p - 1) % 4 == 0).

Algorithm:

Step 1: Create a function generatePythagoreanPrimes(n):

Step 1.1: Initialize a boolean array isPrime of size n + 1 and set all elements to true. This array will be used to mark numbers as either prime or not prime.

Step 1.2: Set isPrime[0] and isPrime[1] to false, as 0 and 1 are not prime numbers. Initialize an empty list pythagoreanPrimes to store Pythagorean Primes.

Step 2: Start iterating from the smallest prime number, which is 2, up to the square root of n. For each prime number p, do the following:

Step 2.1: Check if p is marked as prime (i.e., isPrime[p] is true). If it is, then p is a prime number.

Step 2.2: Mark all multiples of p as not prime by setting isPrime[i * p] to false for i from p * p up to n, with increments of p.

Step 2.3:  Check if (p - 1) % 4 == 0. If this condition is met, add p to the pythagoreanPrimes list.

Step 3: After processing all primes up to the square root of n, the pythagoreanPrimes list will contain Pythagorean Primes. Return the pythagoreanPrimes list.

Step 4: Create a function isPythagoreanPrime(m):

Step 4.1: If m is less than or equal to 1, return false because 0 and 1 are not Pythagorean Primes.

Step 4.2: Call the generatePythagoreanPrimes(m) function to get the list of Pythagorean Primes up to m.

Step 4.3: Check if m is present in the list of Pythagorean Primes. If it is, return true; otherwise, return false.

Step 5: In the main function, initialize an integer variable number with the value you want to check for being a Pythagorean Prime.

Step 6: Call the isPythagoreanPrime(number) function to determine whether the number is a Pythagorean Prime.

Step 7: If it returns true, print that the number is a Pythagorean Prime; otherwise, print that the number is not a Pythagorean Prime.

Filename: ModifiedSievePythagoreanPrimeChecker.java

```import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class ModifiedSievePythagoreanPrimeChecker {

// Function to generate a list of Pythagorean Primes using modified Sieve of Eratosthenes

static List generatePythagoreanPrimes(int n) {

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true);

isPrime[0] = isPrime[1] = false;

List pythagoreanPrimes = new ArrayList<>();

for (int p = 2; p * p <= n; p++) {

if (isPrime[p]) {

for (int i = p * p; i <= n; i += p) {

isPrime[i] = false;

}

if ((p - 1) % 4 == 0) {

}

}

}

return pythagoreanPrimes;

}

// Function to check if a number is a Pythagorean Prime

static boolean isPythagoreanPrime(int n) {

if (n <= 1) {

return false; // 0 and 1 are not Pythagorean Primes

}

List pythagoreanPrimes = generatePythagoreanPrimes(n);

return pythagoreanPrimes.contains(n);

}

public static void main(String[] args) {

int number = 17; // Replace with the number you want to check

if (isPythagoreanPrime(number)) {

System.out.println(number + " is a Pythagorean Prime.");

} else {

System.out.println(number + " is not a Pythagorean Prime.");

}

}

}```

Output:

`17 is not a Pythagorean Prime. `

Time Complexity:

The isPythagoreanPrime(n) function calls generatePythagoreanPrimes(n) to generate Pythagorean Primes up to n, which takes O(n * log(log(n))) time. Checking if m is present in the list of Pythagorean Primes takes O(k) time, where k is the number of Pythagorean Primes up to n.

The overall time complexity of this function is O(n * log(log(n))) + O(k).

Space Complexity:

The space complexity of the generatePythagoreanPrimes(n) function is O(n). Additional space is used for the list of Pythagorean Primes, which can have at most O(n / log(n)) elements.

The overall space complexity of this function is O(n) + O(n / log(n)).

## Approach: Use a Precomputed List of Pythagorean Primes

In this approach, we utilize a precomputed list of Pythagorean Primes up to a specific limit. Instead of generating Pythagorean Primes on the fly, we rely on a predefined list for efficient lookups. This approach is particularly useful when you need to check Pythagorean Primes frequently within a known range, saving computation time.

Algorithm:

Step 1: Create a precomputed list of Pythagorean Primes up to a certain limit. This list contains all known Pythagorean Primes within the specified range.

Step 2: Create a function isPythagoreanPrime(n) to check if a given number n is a Pythagorean Prime.

Step 2.1: Iterate through the precomputed list of Pythagorean Primes. For each prime number prime in the list, compare it to n. If the prime is equal to n, return true because n is a Pythagorean Prime.

Step 2.2: If the loop completes without finding a match, return false because n is not a Pythagorean Prime.

Step 3: In the main function, initialize an integer variable number with the value you want to check for being a Pythagorean Prime.

Step 4: Call the isPythagoreanPrime(number) function to determine whether the number is a Pythagorean Prime.

Step 4.1: If the isPythagoreanPrime function returns true, print that the number is a Pythagorean Prime.

Step 4.2: If the isPythagoreanPrime function returns false, print that the number is not a Pythagorean Prime.

Filename: PrecomputedPythagoreanPrimeChecker.java

```public class PrecomputedPythagoreanPrimeChecker {

// Precomputed list of Pythagorean Primes up to a certain limit

static int[] pythagoreanPrimes = {5, 13, 17, 29, 37, 41, 53, 61, 73, 89};

// Function to check if a number is a Pythagorean Prime using a precomputed list

static boolean isPythagoreanPrime(int n) {

for (int prime : pythagoreanPrimes) {

if (prime == n) {

return true;

}

}

return false;

}

public static void main(String[] args) {

int number = 17; // Replace with the number you want to check

if (isPythagoreanPrime(number)) {

System.out.println(number + " is a Pythagorean Prime.");

} else {

System.out.println(number + " is not a Pythagorean Prime.");

}

}

}```

Output:

`17 is a Pythagorean Prime.`

Time Complexity:

In isPythagoreanPrime(n) function, we iterate through the pythagoreanPrimes list, which contains known Pythagorean Primes up to a certain limit. The time complexity of this iteration is O(k), where k is the number of known Pythagorean Primes in the list.

Overall time complexity is O(k).

Space Complexity:

The pythagoreanPrimes list contains known Pythagorean Primes up to a certain limit. The space complexity is O(k), where k is the number of known Pythagorean Primes in the list.

Overall space complexity is O(k).

## Conclusion:

The choice of approach depends on the specific requirements of your application. If you need to check a single number, the mathematical approach or trial division with a special check is efficient. If you need to check multiple numbers in a range, using a precomputed list or the modified Sieve of Eratosthenes approach is efficient.

The Sieve of Eratosthenes approach is suitable when generating primes is a primary requirement, and Pythagorean Primes need to be identified among them.