Python — код простых чисел

Я пытаюсь найти простой делитель числа 705561475143.

В моем коде функция primeFactor() ищет все множители в некотором целом числе, подставляет их в функцию Prime(), которая либо меняет число на 0, либо не меняет его вообще. Если число не изменилось на 0, это простое число, которое следует добавить в список.

import math


def Prime(n):
    isPrime = False
    r = range(2, int(math.sqrt(n)+5))
    a = 1
    for b in r:
        if r[a] >= int(math.sqrt(n)+2):
            break
        elif n % r[a] != 0:
            a += 1
        elif n % r[a] == 0 & n != r[a] & n != 1:
            n = 0
            break

def primeFactor(m):
    l = []
    for x in range(1, m+1):
        if m % x == 0:
            if Prime(m) != 0:
                l.append(x)
    print(l)

Однако, когда я ввожу

> primeFactor(36)

я получил

> [1,2,3,4,6,9,12,18,36]

Вместо

> [2,3]

И когда я ввожу

> primeFactor(705561475143)

Код не может дать мне ответ.


python prime-factoring
person LaPXL8R    schedule 24.11.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Во-первых, почему вы используете m+1 вместо x in range()? Обратите внимание, что вы можете использовать только range(2, m/2, 1) — посмотрите, сможете ли вы понять, почему.

Во-вторых,

    if m % x == 0:
        if Prime(m) != 0:
            l.append(x)

Если m делится на x, то оно не может быть простым, и вызов Prime(m) бесполезен. Я подозреваю, что вы хотели передать x в качестве аргумента. (Предположим, что x не равно 0 или == m)

В-третьих, Prime() никогда ничего не возвращает. Это означает, что это всегда != 0.

Наконец, чтобы немного помочь вам, я ссылаю вас на некоторые из моих собственных ответов на этот вопрос< /а>.

person Vikram Saran    schedule 24.11.2013
comment
Спасибо. Я попытался запустить это, но оно не распознало некоторые функции (например, PrimeList). Какой импорт вы дополнительно использовали? - person LaPXL8R; 25.11.2013
comment
@LaPXL8R - я намеренно не включил PrimeList(). Однако в итоге я потратил час или около того на настройку своего кода, чтобы сделать его более оптимизированным, сейчас я обновлю этот пост. - person Vikram Saran; 25.11.2013