4. Prime factors

VCMNA221: level 6: Design algorithms involving branching and iteration to solve specific classes of mathematical problems

  • implementing algorithms such as the Euclidean division algorithm

4.1. Prime factor list

The modulus operator can be used to test for a remainder when division is carried out.
Steps:

  • Check if 2 goes into the number, num, with no remainder.

  • While 2 goes into the number exactly, add 2 to the list of prime factors and divide the number by 2.

  • For every odd number from 3 up to the square root of the number, check if the odd number goes in exactly.

  • While the factor goes in exactly, add it to the prime factors list and divide the number, num, by the factor.

  • Return the list of prime factors.

 1import random
 2import math
 3
 4
 5def get_prime_factors(num):
 6    max_possible = int(math.sqrt(num)) + 1
 7    prime_factors = list()
 8    while num % 2 == 0:
 9        prime_factors.append(2)
10        num = num // 2
11    for factor in range(3, max_possible, 2):
12        while num % factor == 0:
13            prime_factors.append(factor)
14            num = num // factor
15    if num > 2:
16        prime_factors.append(num)
17    return prime_factors
18
19
20for _ in range(10):
21    num = random.randint(12, 300)
22    fact  = get_prime_factors(num)
23    print(num, fact)
Sample output is:
97 [97]
235 [5, 47]
96 [2, 2, 2, 2, 2, 3]
256 [2, 2, 2, 2, 2, 2, 2, 2]
210 [2, 3, 5, 7]
247 [13, 19]
78 [2, 3, 13]
194 [2, 97]
34 [2, 17]
47 [47]

4.2. Prime factor lists

The following code checks all the numbers from 2 to 100 for prime factors and lists those with atleast 3 different prime factors.
A crictical line of code is: if len(set(fact)) > 2: which converts the list of prime factors to a set, which can only include one copy of each prime factor.
 1import math
 2
 3
 4def get_prime_factors(num):
 5    max_possible = int(math.sqrt(num)) + 1
 6    prime_factors = list()
 7    while num % 2 == 0:
 8        prime_factors.append(2)
 9        num = num // 2
10    for factor in range(3, max_possible, 2):
11        while num % factor == 0:
12            prime_factors.append(factor)
13            num = num // factor
14    if num > 2:
15        prime_factors.append(num)
16    return prime_factors
17
18
19for num in range(2, 101):
20    fact  = get_prime_factors(num)
21    if len(set(fact)) > 2:
22        print(num, fact)
23
Sample output is:
30 [2, 3, 5]
42 [2, 3, 7]
60 [2, 2, 3, 5]
66 [2, 3, 11]
70 [2, 5, 7]
78 [2, 3, 13]
84 [2, 2, 3, 7]
90 [2, 3, 3, 5]