Я пытаюсь изучить Python-программирование, и я довольно новичок в этом.
У меня возникали проблемы с печатью ряда простых чисел от одной до сотни. Я не могу понять, что не так с моим кодом.
Вот что я написал; он печатает все нечетные числа вместо простых чисел:
for num in range(1,101):
for i in range(2,num):
if (num%i==0):
break
else:
print(num)
break
Вам нужно проверить все числа от 2 до n-1 (на самом деле до sqrt (n), но хорошо, пусть это будет n). Если n делится на любое из чисел, оно не простое. Если число простое, выведите его.
for num in range(2,101):
prime = True
for i in range(2,num):
if (num%i==0):
prime = False
if prime:
print num
Вы можете написать то же самое намного короче и более питонично:
for num in range(2,101):
if all(num%i!=0 for i in range(2,num)):
print num
Как я уже сказал, было бы лучше проверять делители не от 2 до n-1, а от 2 до sqrt (n):
import math
for num in range(2,101):
if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
print num
Для небольших чисел, таких как 101, это не имеет значения, но для 10 ** 8 разница будет очень большой.
Вы можете немного улучшить его, увеличив диапазон, который вы проверяете, на 2 и, таким образом, проверяя только нечетные числа. Вот так:
import math
print 2
for num in range(3,101,2):
if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
print num
Отредактировано:
Так как в первом цикле выбраны нечетные числа, во втором цикле нет необходимости проверять четные числа, поэтому значение 'i' можно начинать с 3 и пропускать до 2.
import math
print 2
for num in range(3,101,2):
if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
print num
break завершает цикл, в котором он находится. Таким образом, вы только проверяете, делится ли он на 2, давая вам все нечетные числа.
for num in range(2,101):
for i in range(2,num):
if (num%i==0):
break
else:
print(num)
что, как говорится, есть намного лучшие способы найти простые числа в python, чем это.
for num in range(2,101):
if is_prime(num):
print(num)
def is_prime(n):
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
Вместо пробного разделения лучший подход, изобретенный греческим математиком Эратосфеном более двух тысяч лет назад, заключается в том, чтобы просеять, многократно изгоняя кратные простые числа.
Начните с составления списка всех чисел от 2 до максимального желаемого числа n. Затем многократно принимайте наименьшее непересекающееся число и вычеркивайте все его кратные числа; числа, которые остаются непересекающимися, являются просторными.
Например, рассмотрите числа, меньшие 30. Сначала 2 обозначается как простой, затем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 и 30 являются вычеркнуто. Следующие 3 обозначены как простые, затем 6, 9, 12, 15, 18, 21, 24, 27 и 30 вычеркнуты. Следующий штрих равен 5, поэтому 10, 15, 20, 25 и 30 вычеркнуты. И так далее. Цифры остаются неизменными: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.
def primes(n):
sieve = [True] * (n+1)
for p in range(2, n+1):
if (sieve[p]):
print p
for i in range(p, n+1, p):
sieve[i] = False
Оптимизированная версия сита обрабатывает 2 отдельно и решает только нечетные числа. Кроме того, поскольку все композиты, меньшие квадрата текущего штриха, пересекаются меньшими штрихами, внутренний цикл может начинаться с p ^ 2 вместо p, а внешний цикл может останавливаться у квадратного корня n. Я оставлю оптимизированную версию для работы.
Я сторонник того, чтобы не принимать лучшее решение и не тестировать его. Ниже приведены некоторые изменения, которые я сделал для создания простых классов примеров, как с помощью @igor-chubin, так и с @user448810. Прежде всего позвольте мне сказать, что это отличная информация, спасибо вам, ребята. Но я должен признать @user448810 за его умное решение, которое оказалось самым быстрым на сегодняшний день (из тех, что я тестировал). Так тебе, сэр! Во всех примерах я использую значения 1 миллион (1 000 000) в виде n.
Пожалуйста, не стесняйтесь попробовать код.
Удачи!
Метод 1, как описано Игорем Чубиным:
def primes_method1(n):
out = list()
for num in range(1, n+1):
prime = True
for i in range(2, num):
if (num % i == 0):
prime = False
if prime:
out.append(num)
return out
Тест: Более 272 секунд
Метод 2, как описано Игорем Чубиным:
def primes_method2(n):
out = list()
for num in range(1, n+1):
if all(num % i != 0 for i in range(2, num)):
out.append(num)
return out
Тест: 73.3420000076 секунд
Метод 3, как описано Игорем Чубиным:
def primes_method3(n):
out = list()
for num in range(1, n+1):
if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
out.append(num)
return out
Тест: 11.3580000401 секунд
Метод 4, как описано Игорем Чубиным:
def primes_method4(n):
out = list()
out.append(2)
for num in range(3, n+1, 2):
if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
out.append(num)
return out
Тест: 8.7009999752 секунд
Метод 5, как описано user448810 (что я считал довольно умным):
def primes_method5(n):
out = list()
sieve = [True] * (n+1)
for p in range(2, n+1):
if (sieve[p]):
out.append(p)
for i in range(p, n+1, p):
sieve[i] = False
return out
Тест: 1.12000012398 секунд
Примечания: Решение 5, перечисленное выше (как было предложено user448810), оказалось самым быстрым и честно тихим творческим и умным. Я люблю это. Спасибо, ребята!
EDIT: О, и, кстати, я не чувствовал необходимости импортировать математическую библиотеку для квадратного корня из значения, поскольку эквивалент просто (n **. 5). В противном случае я не редактировал много других, а затем возвращал значения в массив и возвращал массив. Кроме того, было бы, вероятно, немного более эффективно хранить результаты в файле, чем подробные, и могло бы сэкономить много на памяти, если бы это было просто по одному, но стоило бы немного больше времени из-за записи на диск. Я думаю, что всегда есть место для улучшения. Так что, надеюсь, код имеет смысл парней.
Функциональный модуль программы Python, который возвращает 1'-N простых чисел:
def get_primes(count):
"""
Return the 1st count prime integers.
"""
result = []
x=2
while len(result) in range(count):
i=2
flag=0
for i in range(2,x):
if x%i == 0:
flag+=1
break
i=i+1
if flag == 0:
result.append(x)
x+=1
pass
return result
Лучший способ решить указанную выше проблему - использовать алгоритм "Миллион Рабина". Он использует вероятностный подход, чтобы найти, является ли число простым или нет. И это самый эффективный алгоритм, с которым я столкнулся для этого.
Ниже приведен пример реализации python:
def miller_rabin(n, k):
# Implementation uses the Miller-Rabin Primality Test
# The optimal number of rounds for this test is 40
# See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
# for justification
# If number is even, it a composite number
if n == 2:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in xrange(k):
a = random.randrange(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in xrange(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
Мой способ перечисления простых чисел на номер записи без лишних хлопот использует свойство, которое позволяет получить любое число, которое не является простым с суммированием простых чисел.
Следовательно, если вы разделите номер записи со всеми штрихами ниже нее, и он не делится ни на один из них, вы знаете, что у вас есть простое.
Конечно, есть еще более быстрые способы получения простых чисел, но этот уже выполняется достаточно хорошо, особенно потому, что вы не делите номер записи на любое число, а довольно простые числа вплоть до этого числа.
С помощью этого кода мне удалось на моем компьютере перечислить все простые числа до 100 000 менее чем за 4 секунды.
import time as t
start = t.clock()
primes = [2,3,5,7]
for num in xrange(3,100000,2):
if all(num%x != 0 for x in primes):
primes.append(num)
print primes
print t.clock() - start
print sum(primes)
Распечатайте n простых чисел с помощью python:
num = input('get the value:')
for i in range(2,num+1):
count = 0
for j in range(2,i):
if i%j != 0:
count += 1
if count == i-2:
print i,
Ответ Игоря Чубина может быть улучшен. При тестировании, если X является простым, алгоритм не должен проверять каждое число до квадратного корня из X, он должен проверять только простые числа до sqrt (X). Таким образом, он может быть более эффективным, если он ссылается на список простых чисел по мере его создания. Функция ниже выводит список всех простых чисел под b, что удобно в виде списка по нескольким причинам (например, когда вы хотите узнать количество простых чисел < b). Проверяя простые числа, он экономит время при более высоких числах (сравните около 10 000, разница резко).
from math import sqrt
def lp(b)
primes = [2]
for c in range(3,b):
e = round(sqrt(c)) + 1
for d in primes:
if d <= e and c%d == 0:
break
else:
primes.extend([c])
return primes
Здесь простая и интуитивно понятная версия проверки того, является ли это простым в функции RECURSIVE!:) (Я сделал это как домашнее задание для класса MIT) В python он работает очень быстро до 1900 года. Если вы попробуете более 1900, вы получите интересную ошибку:) (Хотелось бы узнать, сколько номеров может контролировать ваш компьютер?)
def is_prime(n, div=2):
if div> n/2.0: return True
if n% div == 0:
return False
else:
div+=1
return is_prime(n,div)
#The program:
until = 1000
for i in range(until):
if is_prime(i):
print i
Конечно... если вам нравятся рекурсивные функции, этот небольшой код может быть обновлен со словарем, чтобы серьезно увеличить его производительность и избежать этой смешной ошибки. Здесь просто обновление уровня 1 с интеграцией MEMORY:
import datetime
def is_prime(n, div=2):
global primelist
if div> n/2.0: return True
if div < primelist[0]:
div = primelist[0]
for x in primelist:
if x ==0 or x==1: continue
if n % x == 0:
return False
if n% div == 0:
return False
else:
div+=1
return is_prime(n,div)
now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
if is_prime(i):
primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."
finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"
Вот резули, где я напечатал последние 100 простых чисел.
время и дата: 2013-10-15 13: 32: 11.674448
Есть 9594 простых чисел, до 100000
[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99439, 99431, 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99137, 99133, 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897]...
Для его вычисления потребовался ваш компьютер 0: 00: 40.871083.
Так что для моего ноутбука i7 потребовалось 40 секунд, чтобы вычислить его.:)
def prime_number(a):
yes=[]
for i in range (2,100):
if (i==2 or i==3 or i==5 or i==7) or (i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0 and i%(i**(float(0.5)))!=0):
yes=yes+[i]
print (yes)
# computes first n prime numbers
def primes(n=1):
from math import sqrt
count = 1
plist = [2]
c = 3
if n <= 0 :
return "Error : integer n not >= 0"
while (count <= n - 1): # n - 1 since 2 is already in plist
pivot = int(sqrt(c))
for i in plist:
if i > pivot : # check for primae factors 'till sqrt c
count+= 1
plist.append(c)
break
elif c % i == 0 :
break # not prime, no need to iterate anymore
else :
continue
c += 2 # skipping even numbers
return plist
min=int(input("min:"))
max=int(input("max:"))
for num in range(min,max):
for x in range(2,num):
if(num%x==0 and num!=1):
break
else:
print(num,"is prime")
break
Вы заканчиваете цикл слишком рано. После того, как вы проверили все возможности в теле цикла for, а не сломались, число будет простым. Поскольку один не является простым, вам нужно начинать с 2:
for num in xrange(2, 101):
for i in range(2,num):
if not num % i:
break
else:
print num
В более быстром решении вы пытаетесь разделить на простые числа, которые меньше или равны корню числа, которое вы тестируете. Это может быть достигнуто путем запоминания всех простых чисел, которые вы уже нашли. Кроме того, вам нужно только проверить нечетные числа (кроме 2). Вы можете поместить полученный алгоритм в генератор, чтобы вы могли использовать его для хранения простых в контейнере или просто распечатывать их:
def primes(limit):
if limit > 1:
primes_found = [(2, 4)]
yield 2
for n in xrange(3, limit + 1, 2):
for p, ps in primes_found:
if ps > n:
primes_found.append((n, n * n))
yield n
break
else:
if not n % p:
break
for i in primes(101):
print i
Как вы можете видеть, нет необходимости вычислять квадратный корень, быстрее хранить квадрат для каждого простого числа и сравнивать каждый делитель с этим числом.
Это пример программы, которую я написал, чтобы проверить, является ли число простым или нет.
def is_prime(x):
y=0
if x<=1:
return False
elif x == 2:
return True
elif x%2==0:
return False
else:
root = int(x**.5)+2
for i in xrange (2,root):
if x%i==0:
return False
y=1
if y==0:
return True
n = int(raw_input('Enter the integer range to find prime no :'))
p = 2
while p<n:
i = p
cnt = 0
while i>1:
if p%i == 0:
cnt+=1
i-=1
if cnt == 1:
print "%s is Prime Number"%p
else:
print "%s is Not Prime Number"%p
p+=1
Использование функции фильтра.
l=range(1,101)
for i in range(2,10): # for i in range(x,y), here y should be around or <= sqrt(101)
l = filter(lambda x: x==i or x%i, l)
print l
for num in range(1,101):
prime = True
for i in range(2,num/2):
if (num%i==0):
prime = False
if prime:
print num
Как насчет этого? Читая все предложения, я использовал это:
prime=[2]+[num for num in xrange(3,m+1,2) if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1))]
Основные номера до 1000000
[email protected]:/pywork# time python prime.py
78498
real 0m6.600s
пользователь 0m6.532s
sys 0m0.036s
f=0
sum=0
for i in range(1,101):
for j in range(1,i+1):
if(i%j==0):
f=f+1
if(f==2):
sum=sum+i
print i
f=0
print sum
Самая быстрая и лучшая реализация пропусков простых чисел:
def PrimeRanges2(a, b):
arr = range(a, b+1)
up = int(math.sqrt(b)) + 1
for d in range(2, up):
arr = omit_multi(arr, d)
Вот другой подход, который торгует пространство для более быстрого поиска. Это может быть быстрее всего.
import math
def primes(n):
if n < 2:
return []
numbers = [0]*(n+1)
primes = [2]
# Mark all odd numbers as maybe prime, leave evens marked composite.
for i in xrange(3, n+1, 2):
numbers[i] = 1
sqn = int(math.sqrt(n))
# Starting with 3, look at each odd number.
for i in xrange(3, len(numbers), 2):
# Skip if composite.
if numbers[i] == 0:
continue
# Number is prime. Would have been marked as composite if there were
# any smaller prime factors already examined.
primes.append(i)
if i > sqn:
# All remaining odd numbers not marked composite must be prime.
primes.extend([i for i in xrange(i+2, len(numbers), 2)
if numbers[i]])
break
# Mark all multiples of the prime as composite. Check odd multiples.
for r in xrange(i*i, len(numbers), i*2):
numbers[r] = 0
return primes
n = 1000000
p = primes(n)
print "Found", len(p), "primes <=", n
Я был вдохновлен Игорем и сделал блок кода, который создает список:
def prime_number():
for num in range(2, 101):
prime = True
for i in range(2, num):
if (num % i == 0):
prime = False
if prime and num not in num_list:
num_list.append(num)
else:
pass
return num_list
num_list = []
prime_number()
print(num_list)
В дополнение к принятому ответу можно добиться дальнейшей оптимизации, используя список для хранения простых чисел и распечатывая их после генерации.
import math
Primes_Upto = 101
Primes = [2]
for num in range(3,Primes_Upto,2):
if all(num%i!=0 for i in Primes):
Primes.append(num)
for i in Primes:
print i
Вот самая простая логика для начинающих, чтобы получить простые числа:
p=[]
for n in range(2,50):
for k in range(2,50):
if n%k ==0 and n !=k:
break
else:
for t in p:
if n%t ==0:
break
else:
p.append(n)
print p
a=int(input('enter the lower no.'))
b=int(input('enter the higher no.'))
print("Prime numbers between",a,"and",b,"are:")
for num in range(a,b):
if num>1:
for i in range(2,num):
if (num%i)==0:
break
else:
print(num)
def fac(n):
res = []
for i in range(1,n+1):
if n%i == 0:
res.append(i)
def prime(n):
return(fac(n) == [1,n])
def prime_list(n):
pri_list = []
for i in range(1,n+1):
if prime(i)
pri_list.append(i)
return(pri_list)
Более простым и эффективным способом решения этой проблемы является сохранение всех найденных ранее простых чисел и проверка, является ли следующее число кратным любому из меньших простых чисел.
n = 1000
primes = [2]
for i in range(3, n, 2):
if not any(i % prime == 0 for prime in primes):
primes.append(i)
print(primes)
Обратите внимание, что any функция является функцией короткого замыкания, другими словами, она разорвет цикл, как только будет найдено истинное значение.
мы можем составить список простых чисел, используя библиотеку sympy
import sympy
lower=int(input("lower value:")) #let it be 30
upper=int(input("upper value:")) #let it be 60
l=list(sympy.primerange(lower,upper+1)) #[31,37,41,43,47,53,59]
print(l)
Добавление моей собственной версии, просто чтобы показать некоторые трюки itertools v2.7:
import itertools
def Primes():
primes = []
a = 2
while True:
if all(itertools.imap(lambda p : a % p, primes)):
yield a
primes.append(a)
a += 1
# Print the first 100 primes
for _, p in itertools.izip(xrange(100), Primes()):
print p