Chen prime number in Java
Introduction:
A "Chen Prime" is a type of prime number with a specific property related to its neighboring numbers. It is a prime number p such that p+2 is either a prime or a semiprime (the product of two prime numbers).
Chen Primes is named after the Chinese mathematician Chen Jingrun, who significantly contributed to number theory.
Example:
Chen prime numbers up to 100:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89]
Approach: Brute Force
The brute force approach is the most straightforward approach where you iterate through numbers, check if each number is a prime, and then check if p + 2 is either a prime or a semiprime.
Algorithm:
Step 1: Initialize an empty list chenPrimes to store the Chen prime numbers. Iterate through numbers from 2 to limit.
Step 2: For each num in this range, do the following. Check if num is a prime number using the isPrime function.
Step 2.1: If the num is less than or equal to 1, skip to the next iteration. For i, starting from 2 to the square root of num, do. If num is divisible by i, set a flag to indicate that num is not prime and break the loop.
Step 2.2: If the flag is not set (i.e., num is not divisible by any number between 2 and its square root), then num is prime. If num is prime, calculate numPlus2 as num + 2.
Step 3: Check if numPlus2 is either prime or a semiprime (the product of two prime numbers) using the isPrime and isSemiPrime functions. For i starting from 2 to the square root of numPlus2, do:
Step 3.1: If numPlus2 is divisible by i, calculate factor1 as i and factor2 as numPlus2 / i. Check if both factor1 and factor2 are prime using the isPrime function.
Step 3.2: If both factor1 and factor2 are primes, numPlus2 is a semiprime, and the loop can be exited early. After the loop, if numPlus2 is not a semiprime, check if it's prime using the isPrime function.
Step 3.3: If num satisfies the Chen prime criteria (i.e., num is prime, and numPlus2 is either prime or a semiprime), add num to the chenPrimes list.
Step 4: Once the loop through numbers from 2 to limit is complete, print the list chenPrimes, which contains all the Chen prime numbers found within the specified range.
Filename: ChenPrimes.java
import java.util.ArrayList;
import java.util.List;
public class ChenPrimes {
public static void main(String[] args) {
int limit = 100; // You can change this limit to find Chen primes within a different range.
List chenPrimes = new ArrayList<>();
for (int num = 2; num <= limit; num++) {
if (isPrime(num)) {
int numPlus2 = num + 2;
if (isPrime(numPlus2) || isSemiPrime(numPlus2)) {
chenPrimes.add(num);
}
}
}
System.out.println("Chen prime numbers up to " + limit + ": " + chenPrimes);
}
//function to check if a number is prime.
private static boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
//function to check if a number is a semiprime (product of two prime numbers).
private static boolean isSemiPrime(int num) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
int factor1 = i;
int factor2 = num / i;
return isPrime(factor1) && isPrime(factor2);
}
}
return false;
}
}
Output:
Chen prime numbers up to 100: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89]
Time Complexity:
In the isSemiPrime function, we again iterate up to the square root of the current number num, which has a time complexity of O(sqrt(n)). Since we perform this operation for each num from 2 to limit, the overall time complexity for finding semiprimes is also approximately O(limit * sqrt(limit)).
Space Complexity:
The space required to store this list depends on the number of Chen prime numbers within the specified range. In the worst case, where every number from 2 to limit is a Chen prime, the space complexity is O(limit).
Approach: Using Chen Prime Formula
Chen prime formulas are specific formulas and algorithms that can generate Chen primes directly without iterating through numbers. One example is a formula like (5 * n) + 4, which generates Chen primes. You can use such formulas to generate Chen primes without prime checking.
Algorithm:
Step 1: Initialize an empty list chenPrimes to store the Chen prime numbers. Iterate through numbers n starting from 1 and incrementing by 1.
Step 2: For each n, calculate the candidate using the formula (5 * n) + 4. Check if candidate is greater than the specified limit. If it is, break out of the loop since we want to stay within the limit.
Step 3: Check if candidate is either prime or a semiprime (the product of two prime numbers) using a helper function isPrime and the fact that Chen primes are in the form p or p + 2.
Step 4: If the candidate satisfies the Chen prime criteria, add it to the chenPrimes list.
Step 5: Continue the loop, incrementing n and checking the next candidate. When the loop is complete, print the list chenPrimes, which contains all the Chen prime numbers found up to the specified limit.
Filename: ChenPrimesFormula.java
import java.util.ArrayList;
import java.util.List;
public class ChenPrimesFormula {
public static void main(String[] args) {
int limit = 100; // We want to find Chen primes up to 100.
List chenPrimes = generateChenPrimes(limit);
System.out.println("Chen prime numbers up to " + limit + ": " + chenPrimes);
}
//function to check if a number is prime.
private static boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
//function to generate Chen primes using the (5 * n) + 4 formula.
private static List generateChenPrimes(int limit) {
List chenPrimes = new ArrayList<>();
int n = 1;
while (true) {
int candidate = (5 * n) + 4;
if (candidate > limit) {
break; // Stop when we exceed the specified limit.
}
if (isPrime(candidate) || isSemiPrime(candidate)) {
chenPrimes.add(candidate);
}
n++;
}
return chenPrimes;
}
//function to check if a number is a semiprime (product of two prime numbers).
private static boolean isSemiPrime(int num) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
int factor1 = i;
int factor2 = num / i;
return isPrime(factor1) && isPrime(factor2);
}
}
return false;
}
}
Output:
Chen prime numbers up to 100: [9, 14, 19, 29, 34, 39, 49, 59, 69, 74, 79, 89, 94]
Time Complexity:
The loop in the generateChenPrimes function runs until it reaches a candidate greater than the specified limit. In the worst case, this loop iterates until we find enough Chen prime numbers up to the limit.
Therefore, the time complexity of generating Chen primes is O(limit).
Space Complexity:
We maintain a list called chenPrimes to store the Chen prime numbers found. The space required to store this list depends on the number of Chen prime numbers within the specified limit, which is O(limit) in the worst case.