главные факторы для больших чисел - PullRequest
Новая
       7

главные факторы для больших чисел

0 голосов
/ 23 ноября 2018

Я написал это, чтобы определить наибольший простой фактор из любого данного числа.Он хорошо работает для чисел, состоящих менее чем из 9 цифр, но ведет себя неопределенным образом, когда количество цифр превышает девять.Как я могу его оптимизировать?

Эта функция определяет, является ли число простым числом 

def is_prime(x):
    u = 1
    i = 2
    while i < x:
        if x%i == 0:
            u = 0
            break
        else:
            i = i+1
    return u

Эта функция определяет, является ли число простым множителем другого 

def detprime(x,y):
    if x%y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

В этом разделе проверяются все простые множители данного числа, сохраняется их в списке и возвращается наибольшее значение 

def functionFinal(x):
    import math
    factors = []
    y = x//2
    for i in range(1,y):
        if detprime(x,i) == 1:
            factors.append(i)
    y = len(factors)
    print(factors[y-1])

import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)

print (time.process_time () - start_time)

1 Ответ

0 голосов
/ 23 ноября 2018

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

import math
import numba as nb

@nb.njit(cache=True)
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return 0
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return 0
    return 1

@nb.njit(cache=True)
def detprime(x, y):
    if x % y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

@nb.njit(parallel=True)
def functionFinal(x):
    factors = [1]
    y = x // 2
    for i in nb.prange(1, y): # check in parallel
        if detprime(x, i) == 1:
            factors[-1] = i

    return factors[-1]

Так, чтобы 

functionFinal(234675684)

имел сравнение производительности,

Ваш код: 21,490 с

Версия Numba (без параллели): 0,919 с

Версия Numba (с параллелью): 0,580 с

НТН.

...