# Finding the nearest prime number in python 3 7

When it comes to finding the nearest prime number in Python 3, there are several approaches you can take. In this article, we will explore three different solutions to this problem.

## Solution 1: Brute Force

One way to find the nearest prime number is by using a brute force approach. This involves checking each number starting from the given input and iterating upwards until a prime number is found.

``````def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

def find_nearest_prime(n):
if is_prime(n):
return n
lower = n - 1
upper = n + 1
while True:
if is_prime(lower):
return lower
elif is_prime(upper):
return upper
lower -= 1
upper += 1

input_num = 37
nearest_prime = find_nearest_prime(input_num)
print(nearest_prime)``````

This solution works by first checking if the given input is already a prime number. If it is, then it is returned as the nearest prime. Otherwise, it iterates downwards (lower) and upwards (upper) from the input number, checking each number for primality until a prime number is found.

## Solution 2: Sieve of Eratosthenes

Another approach to finding the nearest prime number is by using the Sieve of Eratosthenes algorithm. This algorithm efficiently generates all prime numbers up to a given limit, which can then be used to find the nearest prime number.

``````def sieve_of_eratosthenes(limit):
primes = [True] * (limit + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= limit:
if primes[p]:
for i in range(p * p, limit + 1, p):
primes[i] = False
p += 1
return primes

def find_nearest_prime(n):
primes = sieve_of_eratosthenes(n)
lower = upper = n
while True:
if primes[lower]:
return lower
elif primes[upper]:
return upper
lower -= 1
upper += 1

input_num = 37
nearest_prime = find_nearest_prime(input_num)
print(nearest_prime)``````

This solution first generates all prime numbers up to the given input number using the Sieve of Eratosthenes algorithm. It then iterates downwards (lower) and upwards (upper) from the input number, checking each number against the generated list of primes until a prime number is found.

## Solution 3: Binary Search

A more optimized approach to finding the nearest prime number is by using binary search. This approach takes advantage of the fact that prime numbers are evenly distributed, allowing for a more efficient search.

``````def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

def binary_search(lower, upper):
while lower <= upper:
mid = (lower + upper) // 2
if is_prime(mid):
return mid
elif is_prime(mid - 1):
return mid - 1
elif is_prime(mid + 1):
return mid + 1
if is_prime(mid):
lower = mid + 1
else:
upper = mid - 1
return None

def find_nearest_prime(n):
if is_prime(n):
return n
lower = n - 1
upper = n + 1
return binary_search(lower, upper)

input_num = 37
nearest_prime = find_nearest_prime(input_num)
print(nearest_prime)``````

This solution uses binary search to efficiently find the nearest prime number. It first checks if the given input is already a prime number. If it is, then it is returned as the nearest prime. Otherwise, it performs a binary search between the numbers lower and upper, narrowing down the search range until a prime number is found.

After exploring these three solutions, it is clear that the binary search approach (Solution 3) is the most efficient. It takes advantage of the evenly distributed nature of prime numbers, resulting in a faster search compared to the brute force (Solution 1) and Sieve of Eratosthenes (Solution 2) approaches.

Rate this post

### 6 Responses

1. Jonah says:

Solution 2 sounds like a fancy ancient Greek mathematician, but does it really work better than brute force? 🤔

2. Elian says:

Solution 3 is like finding a needle in a haystack, but with a magnifying glass! Too complicated!

1. Reid Kelly says:

Actually, Solution 3 may seem challenging at first, but it offers a comprehensive and detailed approach. Its like finding the perfect piece to complete a puzzle. Sometimes putting in a little extra effort yields the best results. Keep an open mind!

3. Anthony Herman says:

Solution 2 is the way to go! Sieve of Eratosthenes sounds fancy and efficient.

4. Kayce says:

Personally, I think Solution 2 sounds like a fancy way to find primes. But hey, whatever works!

5. Riley Frost says:

Solution 1: Brute Force sounds cool, but Solution 3: Binary Search has my vote! Whos with me? 🙌