Advertisement
BenTibnam

Slow GCF Algorithm

Apr 13th, 2024
834
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.20 KB | Source Code | 0 0
  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: python math gcf
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement