'Closest Prime Number in Python
I need a user to enter a number and enter out the closest prime number to the value they put in. I am struggling on how to check the prime numbers before and after the number they put in. The last part is to print the smaller value of the two prime numbers if they are the same distance away from the inputted number.
n = int(input("Enter n: "))
holder1 = n
holder2 = n
prime = True
holder3 = 0
holder4 = 0
for i in range(2,n):
if (n % i) == 0:
prime = False
if(prime == True):
print("The prime closest to " + str(n) + " is " + str(n))
else:
while (prime == False):
holder1 -= 1
holder2 += 1
for i in range(2,holder1):
if (n % i) == 0:
prime = False
else:
prime = True
holder3 = holder1
for i in range(2,holder2):
if (n % i) == 0:
prime = False
else:
prime = True
holder4 = holder2
if(abs(n - holder3) <= abs(n-holder4)):
print("The prime closest to " + str(n) + " is " + str(holder3))
elif (abs(n - holder3) > abs(n-holder4)):
print("The prime closest to " + str(n) + " is " + str(holder4))
Solution 1:[1]
If I understood your question correctly, you are trying to find a way of finding the closest number to the inputted number. If this is the case, the Sieve of Eratosthenes method to calculate all of the prime numbers up to a given range, and then find the prime to the number you entered
# Import math for the infinity functionality
import math
# The Sieve of Eratosthenes method of calculating the primes less than the limit
def getPrimes(limit):
# The list of prime numbers
primes = []
# The boolean list of whether a number is prime
numbers = [True] * limit
# Loop all of the numbers in numbers starting from 2
for i in range(2, limit):
# If the number is prime
if numbers[i]:
# Add it onto the list of prime numbers
primes.append(i)
# Loop over all of the other factors in the list
for n in range(i ** 2, limit, i):
# Make them not prime
numbers[n] = False
# Return the list of prime numbers
return primes
# The number to find the closest prime of
number = int(input("Enter a number: > "))
# The list of primes using the function declared above
primes = getPrimes(number + 100)
# The distance away from the closest prime
maxDist = math.inf
# The closest prime
numb = 0
# Loop all of the primes
for p in primes:
# If the prime number is closer than maxDist
if abs(number - p) < maxDist:
# Set maxDist to the number
maxDist = abs(number - p)
# Set numb to the number
numb = p
# Print the output
print(numb, "is the closest prime number to the number you entered!")
I hope this answers your question
***** EDIT *****
You said that you cannot use the python math library, so below is the slightly adjusted code that does not use it:
# The Sieve of Eratosthenes method of calculating the primes less than the limit
def getPrimes(limit):
# The list of prime numbers
primes = []
# The boolean list of whether a number is prime
numbers = [True] * limit
# Loop all of the numbers in numbers starting from 2
for i in range(2, limit):
# If the number is prime
if numbers[i]:
# Add it onto the list of prime numbers
primes.append(i)
# Loop over all of the other factors in the list
for n in range(i ** 2, limit, i):
# Make them not prime
numbers[n] = False
# Return the list of prime numbers
return primes
# The number to find the closest prime of
number = int(input("Enter a number: > "))
# The list of primes using the function declared above
primes = getPrimes(number + 100)
# The distance away from the closest prime
maxDist = 99999999
# The closest prime
numb = 0
# Loop all of the primes
for p in primes:
# If the prime number is closer than maxDist
if abs(number - p) < maxDist:
# Set maxDist to the number
maxDist = abs(number - p)
# Set numb to the number
numb = p
# Print the output
print(numb, "is the closest prime number to the number you entered!")
Solution 2:[2]
Even though I didn't debug your code, the following piece of code should work to find the closest prime number :
n = int(input("Enter n: "))
def chk_prime(n):
if n>1:
for i in range(2, n//2+1):
if n%i==0:
return False
break
else:
return True
else:
return False
if chk_prime(n):
print(f"{n} is itself a prime.")
else:
count = 1
while count<n:
holder1 = n-count
holder2 = n+count
holder1_chk = chk_prime(holder1)
holder2_chk = chk_prime(holder2)
if holder1_chk and holder2_chk:
print(f"closest primes are {holder1}, {holder2}")
break
elif holder1_chk and not holder2_chk:
print(f"closest prime is {holder1}")
break
elif holder2_chk and not holder1_chk:
print(f"closest prime is {holder2}")
break
else:
count = count + 1
First, we define a function specifically to check whether a number is prime or not. Next we initiate count = 1 and create two place-holder values by subtracting count from original number and adding count to the original number. If both of these place-holder values are prime numbers, then we print both of them as closest primes, else the closest one between them.
Solution 3:[3]
I think this is the best way (You can probably comprehend this with python comprehension and some library/built-ins):
def is_prime(n:int) -> bool:
for i in range(int(n**0.5), 1, -2 if int(n**0.5) % 2 == 0 else -1):
if n % i == 0:
return False
return False if n in (0,1) else True
def closest_prime(nt:int) -> int:
if is_prime(nt):
return nt
lower = None
higher = None
for i in range(nt if nt % 2 != 0 else nt-1, 1, -2):
if is_prime(i):
lower = i
break
c = nt+1
while higher == None:
if is_prime(c):
higher = c
else:
c += 2 if c % 2 != 0 else 1
return higher if lower == None or higher-nt < nt-lower else lower
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | Arkistarvh Kltzuonstev |
| Solution 3 | Aceod |