Возвращает наименьшее простое число, которое является делителем x

Question

Следующий код содержит ошибку, которая может вызвать бесконечное l oop, я не могу понять, как заставить работать второй оператор печати, я уверен, что это что-то простое, чтобы исправить это, но просто не могу посмотри.

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n <= x:
        if x % n == 0:
            x += 1
            return n

print(smallest_prime_factor(12)) # should be 2
print(smallest_prime_factor(15)) # should be 3

Answer 1

Вместо увеличения значения для x, которое является числом, для которого вы пытаетесь найти наименьший коэффициент простого числа, вам нужно увеличить n, которое является фактором. Кроме того, если n делит x, то вам нужно вернуть n, иначе вам нужно увеличить значение n вне блока if.

Попробуйте этот код:

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n <= x:
        if x % n == 0:
            return n
        n += 1

Кроме того, чтобы еще больше оптимизировать его, вам нужно просто запустить while l oop до квадрата root числа, чтобы найти его коэффициент простого числа, иначе само число является главным фактором. Так что это оптимизированная версия кода выше:

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    while n*n <= x:
        if x % n == 0:
            return n
        n += 1
    return x

Answer 2

вы получите бесконечное l oop, потому что вы не измените значение n, если условие возврата не выполнено, так как вы можете видеть, что условие возврата выполняется, только если ваш номер x является кратное 2, вы должны изменить:

if x % n == 0:
    x += 1

на:

while n <= x:
    if x % n == 0:
        return x
    n += 1

, чтобы оптимизировать ваш код, вы можете найти простое число n, чтобы разделить x, то есть меньше чем int(math.sqrt(x) + 1):

import math

def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one
    n = 2
    max_n = int(math.sqrt(x) + 1)
    while n < max_n:
        if x % n == 0:
            return n
        n += 1

    return x

еще лучше, если вы можете использовать Сито Эратосфена , чтобы быстро генерировать простые числа и проверять свои x:

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes(y):
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while q < y:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]


def smallest_prime_factor(x):
    """Returns the smallest prime number that is a divisor of x"""
    # Start checking with 2, then move up one by one

    return next((i for i in gen_primes(int(math.sqrt(x) + 1)) if x % i == 0), x)