# Find the Largest Prime Under a Given Number in Java

In computer science, checking whether a number is prime and finding prime numbers are fundamental tasks. This article explores two effective methods in Java to determine the largest prime number less than or equal to a given input number.

## 1. Understanding Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For instance, 2, 3, 5, 7, 11, and so on, are prime numbers.

## 2. Brute Force Method

If we want to find the largest prime number under a given threshold using a brute force approach in Java, we can iterate through each number from the threshold downwards and check if each number is prime. Here’s an example:

public class LargestPrimeFinder { // Helper method to check if a number is prime private static boolean isPrime(int num) { if (num <= 1) { return false; } // Check divisibility from 2 to num-1 for (int i = 2; i < num; i++) { if (num % i == 0) { return false; } } return true; } // Method to find the largest prime less than a given number using brute force public static int largestPrimeUnder(int n) { if (n <= 2) { return -1; // No prime less than or equal to 2 } // Check numbers from n-1 downwards to 2 for (int i = n - 1; i > 1; i--) { if (isPrime(i)) { return i; } } return -1; // If no prime found (which should not happen for n > 2) } public static void main(String[] args) { int number = 100; int largestPrime = largestPrimeUnder(number); if (largestPrime != -1) { System.out.println("Largest prime under " + number + " is: " + largestPrime); } else { System.out.println("No prime found less than " + number); } } }

In this example:

- The
`isPrime`

method checks if a number is prime by iterating through all numbers from`2`

to`num−1`

and checking for divisibility. - The
`largestPrimeUnder`

method iterates backwards from`n−1`

to`2`

and uses the`isPrime`

method to check if each number is prime. It returns the first prime number it finds. - In the
`main`

method, you can change the`number`

variable to find the largest prime under any desired value.

The output of running the `main`

method with `number = 100`

will be:

**Efficiency Considerations**

The brute force approach has a time complexity of `O(n * sqrt(n))`

due to the nested loops in `isPrime`

. This method is not the most efficient for large values of `n`

as It checks divisibility for each number up to `n−1`

which can be slow for large `n`

.

## 3. Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a specified integer `n`

. It works by iteratively marking the multiples of each prime number starting from 2. Using the Sieve of Eratosthenes is a more efficient algorithm for finding prime numbers up to a certain limit.

### 3.1 Java Implementation with Sieve of Eratosthenes

Below is a Java implementation of the Sieve of Eratosthenes to find the largest prime number under a given number `n`

:

import java.util.*; public class LargestPrimeSieveOfEratosthenes { public static List<Integer> sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.add(i); for (int j = i * 2; j <= n; j += i) { isPrime[j] = false; } } } return primes; } public static int largestPrimeUnder(int n) { if (n <= 1) { return -1; // No prime less than or equal to 1 } List<Integer> primes = sieveOfEratosthenes(n - 1); // Find the largest prime less than n for (int i = primes.size() - 1; i >= 0; i--) { if (primes.get(i) < n) { return primes.get(i); } } return -1; // If no prime found (which should not happen for n > 1) } public static void main(String[] args) { int number = 50; int largestPrime = largestPrimeUnder(number); if (largestPrime != -1) { System.out.println("Largest prime under " + number + " is: " + largestPrime); } else { System.out.println("No prime found less than " + number); } } }

### 3.2 Explanation of the Implementation

- The
`sieveOfEratosthenes`

method implements the Sieve of Eratosthenes algorithm to generate a list of all prime numbers up to`n−1`

. - The
`largestPrimeUnder`

method uses the generated list of primes to find the largest prime number less than a given number`n`

. It iterates backwards through the list of primes until it finds a prime less than`n`

. - In the
`main`

method, you can change the`number`

variable to find the largest prime under any desired value.

If we run the `main`

method with `number = 50`

, the output will be:

Largest prime under 50 is: 47

## 4. Conclusion

In conclusion, we’ve explored different approaches in Java to find the largest prime number under a given threshold. First, we discussed a brute-force approach where we iteratively checked each number downwards from the threshold to 2 to determine if it was prime. Next, we explored a more efficient approach using the Sieve of Eratosthenes algorithm to generate all prime numbers up to *n*−1.

By leveraging these techniques, we can effectively find the largest prime number under a given threshold in Java. Depending on the specific requirements and size of *n*, choosing the appropriate method can optimize the performance of prime number detection within a Java application.

## 5. Download the Source Code

This article was about finding the largest prime under the given number in Java.

**Download**

You can download the full source code of this example here:

**Java largest prime lower threshold**