Рассчитайте все возможные факторы простого числа - PullRequest
Новая
       13

Рассчитайте все возможные факторы простого числа

2 голосов
/ 24 января 2011

Проходил учебник по Python и наткнулся на пример, чтобы проверить, является ли число простым или нет. Я изменил несколько вещей, чтобы в результате отобразился список всех возможных факторов числа, если число не простое, однако код не работал.

Код: 

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
            continue
        if notprime == 1:     
            return number, "is not a prime because of these factors", fnum  
        else:
            return True
num =int(raw_input("Enter number: "))
print isprime(num)

Выход: 

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4])
>>> 
Enter number: 25
Reticulating Splines...
(25, 'is a prime number')

Ожидаемый результат: 

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4, 6])

Enter number: 25
Reticulating Splines...
(25, 'is not a prime because of these factors', [1,5])

Плохая структура управления - это мое предположение, но может ли кто-нибудь исправить мой код?

Я понимаю, как работает range (): в этом случае range () задается начальное и конечное значение, значение шага по умолчанию равно 1. Я понимаю, что продолжить, продолжить цикл, но можно ли его использовать с if? Я думаю, что это неправильно.

UPDATE
Решена проблема с отступом продолжение должно быть для цикла for, то же самое для if ... notprime. 

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return number, "is a prime number"
num =int(raw_input("Enter number: "))
print isprime(num)

Обновление2: (от Thx до @neil)
И continue просто глупо

Обновлен код и сравнение скорости между n / 2 и sqrt (n) Спасибо @neil и @ emmanuel
n / 2 код: v2 

import time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, (number/2)+1):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    end=time.clock()
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum, "Time taken", end-start  
    else:
        return number, "is a prime number. Time Taken", end-start
print "Prime or factor calculator v2 using n/2"
print #
num =int(raw_input("Enter number: "))
print isprime(num)

sqrt (n) код: v3 

import math, time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    end=time.clock()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum ,"Time taken", end-start 
    else:
        return True, "Time taken", end-start

print "Prime or factor calculator v3 using sqrt(n)"
print #

num =int(raw_input("Enter number: "))

print isprime(num)

Вывод (отображается только время)

Время для sqrt (n) кода: v3
Простое или факторный калькулятор v3 с использованием sqrt (n)
Введите номер: 999999
Время истекло ', 0,0022617399697466567

Время для n / 2 кода: v2
Прайм или факторный калькулятор v2 с использованием n / 2
Введите номер: 999999
Время: 0.11294955085074321

Время для исходного кода (n): v1
Премьер или фактор калькулятор v1
Введите номер: 999999
Время: 0,22059172324972565

v1 и v2 не могут обработать номера 999999999, 999999999999 и 999999999999999, оба дали MemoryError

Однако v3 обработал три числа:
999999999: 0,010536255306192288
999999999999: 0,75631930873896636
999999999999999: 24,04511104064909

Оболочка зависает для 9999999999999999 и выдает MemoryError для 999999999999999999

Благодаря @Lennart, я думаю переписать код более удобным для ООП способом, используя классы. Но я, кажется, не делаю это правильно.

Ответы [ 4 ]

1 голос
/ 24 января 2011

@ neil:

"Улучшение, которое вы можете сделать ... состоит в том, чтобы выполнять цикл только до n / 2 - не может быть множителя больше половины числа."

Кстати, самое высокое значение, которое вам нужно проверить, это int(math.ceil(math.sqrt(n))), не нужно переходить к n/2, если каждый раз, когда вы получаете значение, вы получаете соответствующее значение (т. Е. Если a x b = n,* a или b меньше квадратного корня из n, а другой больше): 

def isprime(number):
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return True

Повышение производительности, даже если в конце список не отсортирован (но это можетсделать в цикле, добавив 2 числа p и number / p при хороших показателях).

1 голос
/ 24 января 2011

Вы вернете после тестирования только один номер. Переместите тесты if и возвраты за пределы цикла for.

Кроме того, возвращать True, если это простое число, и строку, если это не так, непрактично. Если вы тогда позвоните 

if isprime(7):

Это всегда будет оцениваться как Истина. Я немного улучшил вещи: 

def factors(number):
    fnum=[]
    for p in range(2, number):
        if (number % p) == 0:
            fnum.append(p)
    return fnum

for x in range(100):
    f = factors(x)
    if f:
        print x, "is not a prime and has factors", f
    else:
        print x, "is a prime"
1 голос
/ 24 января 2011

Проблема в вашем отступе - if notprime==1: не должно быть в цикле for. Он должен иметь только один уровень отступа.

Кроме того, continue не требуется.

EDIT:

Улучшение, которое вы можете сделать (я только что работал над простыми числами для задачи Project Euler прошлой ночью), состоит в том, чтобы выполнять цикл только до n / 2 - коэффициент не может быть больше половины числа.

1 голос
/ 24 января 2011

Ваш последний if notprime ... и три следующие за ним строки имеют слишком большой отступ и, таким образом, выполняются внутри цикла, а не снаружи.

...