# Slow GCF Algorithm

Apr 13th, 2024
834
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import math
2.
3. # how many numbers we're going to find the factors of
4. input_count = 0
5.
6. # where the factors are being stored (2D array)
7. factors = []
8.
9. # function for finding factors
10. def find_and_store(number=0):
11.         number = abs(number) if (number < 0 and number != 1) else 1 if (number == 0) else number
12.
13.         # 1 and number are always factors
14.         n_factors = [1]
15.
16.         # going through possible factors
17.         for i in range(2, number):
18.                 for j in range(i, number):
19.                         product = i * j
20.
21.                         # adding factor to list
22.                         if product == number:
23.                                 n_factors.append(i)
24.
25.                                 # accounting for perfect squares
26.                                 if (i != j):
27.                                         n_factors.append(j)
28.                                 break
29.                         # if the product is greater then the number it isn't a factor
30.                         elif product > number:
31.                                 break
32.
33.                 continue
34.
35.         n_factors.append(number)
36.         factors.append(n_factors)
37.
38.
39. def calculate_gcf():
40.         primary_factors = factors[0]
41.         secondary_factors = factors[1]
42.         gcf = 0
43.
44.         # slow check each factor
45.         for f1 in primary_factors:
46.                 for f2 in secondary_factors:
47.                         if f1 == f2 and f1 > gcf:
48.                                 gcf = f1
49.                                 break
50.
51.         return gcf
52.
53.
54.
55.
56. print("GCF Calculator - Slow Version\n")
57.
58. while True:
59.         number = input("Enter integer to find factors: ")
60.
61.         # any non-number will break out of the program
62.         try:
63.                 # using an exception because I can't get isnan to work as it's suppose to and I just wanted to get this working
64.                 math.isnan(float(number))
65.         except ValueError:
66.                 break
67.
68.         find_and_store(int(number))
69.
70. # if more then one number was entered we can calculate a GCF
71. if len(factors) > 1:
72.         gcf = calculate_gcf()
73.         print(gcf)
74. else:
75.         print("Must provide at least two numbers to calculate a GCF")
Tags: