2
votes

Lors de la recherche des facteurs premiers d'un nombre, certains nombres fonctionnent mais d'autres pas

Lors du test des nombres, certains fonctionnent, par exemple 48, mais d'autres non. Je ne sais pas quelle est la meilleure façon d'aborder la recherche de tous les facteurs d'un nombre.

Factorisation principale

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0              
    if n == 1:
        return 1                
    if n >= 2:
        while n % i == 0:
            next_n = n / i
            factors.append(i)
            n = next_n 
            if n % i != 0:
                i += 1
                continue
            elif i == n:
                break
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

Je m'attends à obtenir une liste de tous les facteurs d'un nombre.

python primes

1 commentaires

La boucle while est laissée (ou jamais entrée) si un i ne peut pas diviser n au moins une fois, peu importe si des valeurs plus élevées pour i le pourraient.

3 Réponses :

0
votes

J'ai changé votre code et maintenant cela fonctionne pour tous les nombres naturels:

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n >= 2:
        while i * i <= n:
            while n % i == 0:
                factors.append(i)
                n = n // i
            i += 1
    if n > 1:
        factors.append(n)
    if len(factors) == 1:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

3 commentaires

merci cela fonctionne mais j'ai quelques questions. Pourquoi avez-vous utilisé "while i * I <= n" dans la première instruction while? Aussi quel est l'intérêt de l'instruction if finale, "if n> 1"

@parth si n est un nombre premier, il a au moins un diviseur non supérieur à sqrt (n), donc "while i * i <= n" trouvera cela; sinon n ne sera jamais divisé par rien et nous vérifierons cela par "n> 1".

En fait, l'utilisation de "i * i <= n" rend l'algorithme plus rapide que l'utilisation de "i <= n". Il transforme un algorithme O (n) en un algorithme O (sqrt (n)).

0
votes

def find_primes(n):
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    while i <= n:
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

0 commentaires

0
votes

La fonction pour calculer les facteurs premiers ci-dessous est beaucoup plus simple que celle ci-dessus. Le reste n'est que la vérification de l'intégrité de l'entrée utilisateur.

###########################################################
#Main function to calculate prime factors
def find_prime_factors(n):
    factors = []
    p = 2
    while n > p ** 2:
        if n % p == 0:
            factors.append(p)
            n //= p
        else:
            p += 1
    factors.append(n)
    return factors
###########################################################

# Get User input
n = input('Enter a number to find all the Prime Factors: ') 

# Check if the entered value is a number
while not n.isnumeric():
    print('Entered number was not numeric.')
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

# Check the entered value is greater than one (1)
# Prime Factor check happens on only positive numbers that are greater than one (1)

while int(n) < 2:
    print("Please enter a positive number that is greater than one (1).")
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

#Python 3.7 string formating
print(f'The prime factor(s) of {n}: {find_prime_factors(int(n))} ')

0 commentaires