Программа для деления числа на два меньших простых числа

Question

У меня очень большое число, и я хочу создать программу, которая найдет два простых числа, которые при умножении дадут исходное число.

Ex.
Original_number = 299

// The program should get these two numbers:

q = 13
p = 23

Программа запускается нормально при запуске, но в определенный момент она просто останавливается, и я не уверен, что не так. Код:

import time
import math

def main():
    time1 = time.clock()
    q  = int(0)
    p = int(0)
    finalnumber = int(377)


    print("in main \n")
    print("q = ", q)
    print("\n p = ", p)

    gotResult = 0

    while(gotResult == 0):

        p = GetNextPrime(p)

        if(p >= finalnumber):
            q = GetNextPrime(q)
            p = q
            p = GetNextPrime(p)

        if(q * p == finalnumber):
            gotResult == 1
            break

    print("q = ", q)
    print("\n p = ", p)
    time2 = time.clock()

    ElapsedTime = time2 - time1
    print("Elapsed time: ", ElapsedTime)


def GetNextPrime(prime):
    print("in GetNextPrime \n")
    isPrime = 0

    while(isPrime == 0):
        prime = prime + 1
        if(IsPrime(prime)== 1):
            isPrime = 1

    return prime

def IsPrime(prime):
    print("in IsPrime \n")
    isPrime = 0
    i = 2

    while(i <= math.sqrt(prime)):
        if(i % 2 == 0):
            i = i+1
        if(prime % i == 0):
            isPrime = 1
            break


    return isPrime

#start of program here
main()

Я написал программу на Python, и я знаю, что она, вероятно, не очень хорошая, потому что я новичок в Python (я программировал на C ++, и я даже не очень хорош в этом) Но я надеюсь, что вы можете помочь мне найти проблему:)

пс. Каков максимальный размер оригинального номера? Сколько может быть шифров?

Answer 1

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

Но вышеприведенный подход довольно расточительный. Я бы предпочел взять список простых чисел, сгенерировать все его пары и умножить. Результатом будет список чисел, который, ну, может быть разложен только на 2 простых числа. Как это:

some_primes = [2, 3, 5, 7, 11] # you can generate a better list
my_numbers = [x*y for x in some_primes for y in some_primes]

Answer 2

Простой подход - пробное деление:

import math
def factors(number):
    return [(x, number / x)  for x in range(int(math.sqrt(number)))[2:] if not number % x]

Затем factors(299) возвращает [(13,23)]

Есть проблемы с этим методом для больших чисел:

1. Большие числа могут превышать предел целого числа Python (находится в sys.maxint). 64-битный компьютер будет ограничен 18 десятичными цифрами.

2. Факторинг больших чисел - сложная проблема, и вопрос исследования остается открытым. Подразделение суда примерно такая же грубая сила, как и сейчас, но оно будет работать для меньшего числа. В противном случае вам быстро понадобится более сложный алгоритм. См. wikipedia для обсуждения.

3. Если вы собираетесь решать грубые численные задачи, Python - не тот язык. Идентичные алгоритмы будут работать быстрее на скомпилированном языке, таком как C ++.

Answer 3

В дополнение к ответам Джохеля Ритцеля и DSM логика в цикле main () while не учитывает случаи, когда число не является произведением двух простых чисел (тогда оно войдет в бесконечный цикл).

Кроме того, если вы рассчитываете использовать действительно большие числа (скажем, более 20-30 цифр), ваш подход, вероятно, слишком медленный. Вы должны использовать сито Erastothenes как минимум, чтобы заранее создать достаточно большой список простых чисел, если хотите получить приемлемые результаты.

Существуют (довольно сложные) алгоритмы для работы с большими случаями, но в целом это сложная проблема, и ее решение очень плохо масштабируется с количеством цифр.

Answer 4

isPrime неверно.Вы возвращаете 1, когда число не простое число.Также вы никогда не проверяете, можно ли разделить число на 2. Я не смотрел дальше.

Подсказка: Python - это не C. Есть True, False и вам не нужны все скобкив if, while.

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

Answer 5

В следующей логике:

while(i <= math.sqrt(prime)):
    if(i % 2 == 0):
        i = i+1
    if(prime % i == 0):
        isPrime = 1
        break

Если я нечетный и простое число не делится им, оно зациклится навсегда, и здесь оно застревает на 3. [Другая очевидная проблема уже была указана.]