Μία συνάρτηση για την εύρεση των πρώτων παραγόντων ενός ακεραίου. Η συνάρτηση επιστρέφει ένα dictionary με ζεύγη τιμών τους παράγοντες του ζητούμενου αριθμού.
Δεν επιστρέφονται διπλά ζεύγη τιμών, δηλαδή για το 6 θα επιστραφεί το {1: 6, 2: 3} και όχι το {1: 6, 2: 3, 3: 2}.
def prime_factors(n):
"""
Returns the prime factors of a given number.
Input
-----
n : Integer
The number whose prime factors are being searched.
Output
------
factors : Dictionary
The factors of n.
"""
factors = {}
# Zero, One and Two are specials cases.
if n == 0:
pass
elif n == 1:
factors[1] = 1
elif n == 2:
factors[1] = 2
else:
factors[1] = n
if n % 2 == 0:
factors[2] = n / 2
# start from number 3
i = 3
while True:
# stop when i is bigger than sqrt(n)
if i >= int(n**0.5) + 1:
break
if n % i == 0:
factors[i] = n / i
# As we started the loop from 3, we calculate only for odd numbers.
i += 2
return factors
Για να ελέγξουμε αν κάποιος αριθμός είναι πρώτος απλά ελέγχουμε αν το μήκος του επιστρεφόμενου dictionary είναι ίσο με 1, δηλαδή: