Python 中最接近的质数
Closest Prime Number in Python
我需要用户输入一个数字并输入最接近他们输入值的素数。我正在努力检查如何检查他们输入的数字前后的素数。最后一部分是如果两个素数与输入数字的距离相同,则打印两个素数中较小的值。
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))
如果我没有正确理解你的问题,那么你正在尝试找到一种方法来找到最接近输入数字的数字。如果是这种情况,Eratosthenes 筛法计算给定范围内的所有素数,然后找到您输入的数字的素数
# 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!")
我希望这能回答你的问题
***** 编辑 *****
你说你不能使用python数学库,所以下面是稍微调整后的不使用它的代码:
# 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!")
即使我没有调试您的代码,以下代码也应该可以找到最接近的素数:
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
首先,我们定义一个函数专门用来判断一个数是否为质数。接下来我们启动 count = 1
并通过从原始数字中减去 count
并将计数添加到原始数字来创建两个占位符值。如果这两个占位符值都是质数,那么我们将它们打印为最接近的质数,否则打印它们之间最接近的一个。
我认为这是最好的方法(你可以通过 python 理解和一些 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
我需要用户输入一个数字并输入最接近他们输入值的素数。我正在努力检查如何检查他们输入的数字前后的素数。最后一部分是如果两个素数与输入数字的距离相同,则打印两个素数中较小的值。
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))
如果我没有正确理解你的问题,那么你正在尝试找到一种方法来找到最接近输入数字的数字。如果是这种情况,Eratosthenes 筛法计算给定范围内的所有素数,然后找到您输入的数字的素数
# 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!")
我希望这能回答你的问题
***** 编辑 *****
你说你不能使用python数学库,所以下面是稍微调整后的不使用它的代码:
# 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!")
即使我没有调试您的代码,以下代码也应该可以找到最接近的素数:
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
首先,我们定义一个函数专门用来判断一个数是否为质数。接下来我们启动 count = 1
并通过从原始数字中减去 count
并将计数添加到原始数字来创建两个占位符值。如果这两个占位符值都是质数,那么我们将它们打印为最接近的质数,否则打印它们之间最接近的一个。
我认为这是最好的方法(你可以通过 python 理解和一些 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