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) {
pythagoreanPrimes.add(p);
}
}
}
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.