Ищите контрпример в этой программе основных факторов python - PullRequest
Новая
       10

Ищите контрпример в этой программе основных факторов python

0 голосов
/ 10 октября 2018

Я собрал воедино этот скрипт, чтобы выложить простую факторизацию целого числа n.В самом конце сценария я умножаю текущий список простых факторов, включая кратность, и проверяю, равен ли он n;если нет, я делю этот продукт и добавляю частное, если оно простое.

Я проверил тонну чисел, и она работала каждый раз, но математически я не уверен, почему.Разве мне не нужно зацикливаться на проверке остатков простых чисел в range (sqrt(n), n)?Не может ли быть целое число с двумя простыми числами в этом диапазоне?Если есть, я еще не смог найти пример.Я новичок в Python, поэтому другое объяснение состоит в том, что я не понимаю свой собственный код, и он как-то зацикливается на мне.

from math import sqrt
n = int(input("Let's factor a number:"))

def isPrime(x):
    for i in range(2,int(sqrt(x)+1)):
        if x%i==0:
            return False
    return True

m = int(sqrt(n)+1)
i = 1
factors = []
while(1 < m):
    if (n % (m**i) == 0 and isPrime(m) == True):
        factors.append(m)
    else:
        m -= 1
        i = 1
        continue
    i += 1

prod = 1
for i in factors:
    prod *= i

if prod == n:
    print(factors)
elif isPrime(n/prod) == True:
    factors.append(int(n/prod))
    print(factors)

1 Ответ

0 голосов
/ 10 октября 2018

Нет, вам не нужен такой цикл.n может иметь только один простой множитель> sqrt(n).Предположим противное: их как минимум два.i, j> sqrt (n).В этом случае i * j должно быть> sqrt (n) * sqrt (n), и в этом ваше противоречие.

Как только вы нашли все факторы, меньшие sqrt(n), все оставшееся число будет простым,и будет единственным фактором больше sqrt(n).

...