Проверка Python Prime Number
Я пытался написать программу, которая будет принимать введенное число, и проверить и посмотреть, является ли это простое число. Код, который я сделал до сих пор, прекрасно работает, если число на самом деле является простым числом. Если число не простое число, оно действует странно. Мне было интересно, если кто-нибудь может сказать мне, что проблема с кодом.
a=2
num=13
while num > a :
if num%a==0 & a!=num:
print('not prime')
a=a+1
else:
print('prime')
a=(num)+1
результат, полученный при 24, равен: не простое, не простое, не простое простое
Как бы я исправить ошибку с отчетным простым на каждом нечетном и не простым для каждого четного
14 ответов
Вам нужно прекратить итерации, если вы знаете, что число не простое. Добавить break как только вы найдете премьер для выхода из цикла while.
Внесите только минимальные изменения в ваш код, чтобы он работал:
a=2
num=13
while num > a :
if num%a==0 & a!=num:
print('not prime')
break
i += 1
else: # loop not exited via break
print('prime')
Ваш алгоритм эквивалентен:
for a in range(a, num):
if a % num == 0:
print('not prime')
break
else: # loop not exited via break
print('prime')
Если вы бросите его в функцию, вы можете обойтись без break и для другого:
def is_prime(n):
for i in range(3, n):
if n % i == 0:
return False
return True
Даже если вы собираетесь использовать грубую силу для простого числа, вам нужно всего лишь пройти до квадратного корня n, Также вы можете пропустить проверку четных чисел после двух.
С этими предложениями:
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
Обратите внимание, что этот код неправильно обрабатывает 0, 1и отрицательные числа.
Мы делаем это проще, используя all с выражением генератора для замены цикла for.
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
def isprime(n):
'''check if integer n is a prime'''
# make sure n is a positive integer
n = abs(int(n))
# 0 and 1 are not primes
if n < 2:
return False
# 2 is the only even prime number
if n == 2:
return True
# all other even numbers are not primes
if not n & 1:
return False
# range starts with 3 and only needs to go up
# the square root of n for all odd numbers
for x in range(3, int(n**0.5) + 1, 2):
if n % x == 0:
return False
return True
Взято из:
def is_prime(n):
return all(n%j for j in xrange(2, int(n**0.5)+1)) and n>1
Две основные проблемы с вашим кодом:
- После обозначения числа не простого, вы продолжаете проверять остальные делители, даже если вы уже знаете, что это не простое число, что может привести к тому, что оно напечатает "простое" после печати "не простое". Подсказка: используйте оператор `break'.
- Вы определяете простое число до того, как проверили все делители, которые нужно проверить, потому что вы печатаете "простое" внутри цикла. Таким образом, вы получаете "простое число" несколько раз, по одному разу для каждого делителя, который неравномерно входит в число тестируемых. Подсказка: используйте
elseПредложение с циклом для печати "премьер", только если цикл выходит без прерывания.
Пара довольно существенных недостатков:
- Вы должны следить за числами, которые вы уже нашли, которые просты и делятся только на них. Зачем делить на 4, если вы уже поделили на 2? Если число делится на 4, оно также делится на 2, так что вы бы его уже поймали, и нет необходимости делить на 4.
- Вам нужно только проверить до квадратного корня тестируемого числа, потому что любой фактор, больший, чем этот, должен быть умножен на число, меньшее этого, и это уже было бы проверено к тому времени, когда вы доберетесь до большего.
Этот пример - используйте Reduce(), но замедлите его:
def makepnl(pnl, n):
for p in pnl:
if n % p == 0:
return pnl
pnl.append(n)
return pnl
def isprime(n):
return True if n == reduce(makepnl, range(3, n + 1, 2), [2])[-1] else False
for i in range(20):
print i, isprime(i)
Он использует Sieve Of Atkin, быстрее чем выше:
def atkin(limit):
if limit > 2:
yield 2
if limit > 3:
yield 3
import math
is_prime = [False] * (limit + 1)
for x in range(1,int(math.sqrt(limit))+1):
for y in range(1,int(math.sqrt(limit))+1):
n = 4*x**2 + y**2
if n<=limit and (n%12==1 or n%12==5):
# print "1st if"
is_prime[n] = not is_prime[n]
n = 3*x**2+y**2
if n<= limit and n%12==7:
# print "Second if"
is_prime[n] = not is_prime[n]
n = 3*x**2 - y**2
if x>y and n<=limit and n%12==11:
# print "third if"
is_prime[n] = not is_prime[n]
for n in range(5,int(math.sqrt(limit))):
if is_prime[n]:
for k in range(n**2,limit+1,n**2):
is_prime[k] = False
for n in range(5,limit):
if is_prime[n]: yield n
def isprime(n):
r = list(atkin(n+1))
if not r: return False
return True if n == r[-1] else False
for i in range(20):
print i, isprime(i)
Начните здесь, поэтому, пожалуйста, дайте мне знать, если я в порядке, но я бы сделал это так:
def prime(n):
count = 0
for i in range(1, (n+1)):
if n % i == 0:
count += 1
if count > 2:
print "Not a prime"
else:
print "A prime"
Ваша проблема в том, что цикл продолжает работать, даже если вы уже "решили". Вы должны добавить строку break после a=a+1
После того, как вы определите, что число составное (не простое), ваша работа завершена. Вы можете выйти из цикла с break,
while num > a :
if num%a==0 & a!=num:
print('not prime')
break # not going to update a, going to quit instead
else:
print('prime')
a=(num)+1
Кроме того, вы можете попытаться познакомиться с некоторыми конструкциями в Python. Ваш цикл может быть сокращен до однострочного, который по-прежнему хорошо читается на мой взгляд.
any(num % a == 0 for a in range(2, num))
Это небольшое изменение в том, что оно отслеживает факторы.
def prime(a):
list=[]
x=2
b=True
while x<a:
if a%x==0:
b=False
list.append(x)
x+=1
if b==False:
print "Not Prime"
print list
else:
print "Prime"
max=int(input("Find primes upto what numbers?"))
primeList=[]
for x in range(2,max+1):
isPrime=True
for y in range(2,int(x**0.5)+1) :
if x%y==0:
isPrime=False
break
if isPrime:
primeList.append(x)
print(primeList)
Проверка простого номера.
def is_prime(x):
if x < 2:
return False
else:
if x == 2:
return True
else:
for i in range(2, x):
if x % i == 0:
return False
return True
x = int(raw_input("enter a prime number"))
print is_prime(x)
Это сделало бы работу:
number=int(raw_input("Enter a number to see if its prime:"))
if number <= 1:
print "number is not prime"
else:
a=2
check = True
while a != number:
if number%a == 0:
print "Number is not prime"
check = False
break
a+=1
if check == True:
print "Number is prime"
a=input("Enter number:")
def isprime():
total=0
factors=(1,a)# The only factors of a number
pfactors=range(1,a+1) #considering all possible factors
if a==1 or a==0:# One and Zero are not prime numbers
print "%d is NOT prime"%a
elif a==2: # Two is the only even prime number
print "%d is prime"%a
elif a%2==0:#Any even number is not prime except two
print "%d is NOT prime"%a
else:#a number is prime if its multiples are 1 and itself
#The sum of the number that return zero moduli should be equal to the "only" factors
for number in pfactors:
if (a%number)==0:
total+=number
if total!=sum(factors):
print "%d is NOT prime"%a
else:
print "%d is prime"%a
isprime()
# is digit prime? we will see (Coder: Chikak)
def is_prime(x):
flag = False
if x < 2:
return False
else:
for count in range(2, x):
if x % count == 0:
flag = True
break
if flag == True:
return False
return True