Уведомления

Группа в Telegram: @pythonsu

#1 Март 18, 2015 02:04:47

Aspergo
Зарегистрирован: 2014-08-31
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Поиск простых чисел

f=range(2,21)
print f
v=f[:]
o=[]
for x in v:
  for y in range(2,x):
    if x%y==0 and x!=y:
      o.append(x)     
print o
Почему при выполнении этого кода, выдается список o, в котором некоторые элементы повторяются:
[2,6,6,8,8,9,10,10,12,12,12,12]
?

f=range(2,6)
print f
v=f[:]
o=[]
for x in v:
  for y in range(2,x):
    if x%y==0:
      f.remove(x)
      print f, v
print f

Почему такой код срабатывает без ошибок?

f=range(2,21)
print f
v=f[:]
o=[]
for x in v:
  for y in range(2,x):
    if x%y==0:
      f.remove(x)
      print f, v
print f
А такой выдает ошибку - x not in list? (Отличие - только в первой строке). Ведь в цикле обходится копия списка, из которого удаляются элементы, а не сам этот список.

И почему обход в цикле списка и удаление из этого же списка элементов срабатывает без ошибок в этом случае:
# -*- coding: utf-8-*-
#z=5*7*13*29
#print z
# 5,7,13 and 2 are prime factors of 13195
#Простое число: имеет только два делителя (1 и оно само)
x=13195
s=[]
r=range(13195/2) # Дальше 13195/2 все равно нет делителей 13195, кроме его самого. 
r.remove(0)
e=range(10)
e.remove(0)
e.remove(1)
for x in r: # Составляем список всех чисел, на которые 13195 делится нацело
  if 13195%x==0:
    s.append(x)
o=[]
for x in s:
    for y in e:
      if x%y==0 and x!=y: # Убираем из них числа, которые нацело делятся на числа от 1 до 10
        o.append(x)
    for z in range(2,x): # Убираем из них числа, которые нацело делятся на простые делители, попавшие в список s
      if x%z==0:
        o.append(x)
for x in o: # Убираем эти числа, которые не простые, получаем список простых делителей 13195
  if x in s:
    s.remove(x)
w=max(s) # Ищем максимальлный простой делитель
print w  # Ответ
См. 4 с конца строку.

PS И, возможно, кто-нибудь знает, откуда вообще взялась цифра в корень из n? https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B
Значительно позже арабский математик ибн ал-Банна предложил делать перебор целых чисел, не до n, а до \sqrt{n}, что позволило уменьшить количество операций.

Отредактировано Aspergo (Март 18, 2015 02:05:37)

Офлайн

#2 Март 18, 2015 03:28:53

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10015
Репутация: +  857  -
Профиль   Отправить e-mail  

Поиск простых чисел

Та же задача.

Aspergo
И, возможно, кто-нибудь знает, откуда вообще взялась цифра в корень из n?
Если число составное, то у него есть два делителя, не равных единице и самому числу. Какие это числа? Либо они равны друг другу (оба равны корню числа), либо одно меньше другого (одно меньше корня, а другое больше).
Поэтому мы и ищем либо равный, либо меньший из делителей.



Отредактировано py.user.next (Март 18, 2015 03:29:48)

Офлайн

#3 Март 18, 2015 17:26:14

Aspergo
Зарегистрирован: 2014-08-31
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Поиск простых чисел

Кажется, понятно. Спасибо

Отредактировано Aspergo (Март 18, 2015 17:43:15)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version