for loop to check if a number in array divides all elements in array

Question

I'm new to coding, and stack Overflow. I just wanted to see what's the BEST approach to solve this problem.

My approach// run a for loop that assigns the number to a variable if it's dividing all elements. Problem is I can't represent the for loop properly. Is my approach wrong? Would you use a dictionary instead? I just need the approach & maybe the loop. THANK YOU!

the greatest common divisor (GCD), also called highest common factor(HCF) of N numbers is the largest positive integer that divides all numbers without giving a remainder. Write an algorithm to determine the GCD of N positive integers.

func generalizedGCD(num:INT, arr:[Int])->Int

num- an integer representing the number of positive integers(N), arr - list of positive integers

input/ num = 5, arr = [2,4,6,8,10] Output/ 2

input/ num = 5, arr = [2,3,4,5,6] output/ 1

You can find a method in https://stackoverflow.com/a/28352004/1187415. — Martin R, Aug 03 '20 at 06:24

score 1 · Accepted Answer · answered Aug 03 '20 at 07:18

A point of attention is that a prime number may enter several times in gcd, hence need for some repeat loops…

let arr = [4, 8, 12] // [2,4,6,8,10]

// 1. build the list of prime numbers (up to 100 is enough to test GCD of numbers upto 10_000). You could also build this list by code.
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

// 2. Find the min in your array. No need to test divisor beyond the min, to speed up
var minimum = arr.min() ?? 1

// 3. Loop through primes to test as divisor or minumum element
var goOn = true
var possibleDivisors : [Int] = []
for prime in primes where minimum > 1 {
    var primeAtPower = 1
    repeat {        // A same prime may be multiple times in gcd. ex: arr = [4, 8, 12]: 2 will appear twice as divisor of 4
        if minimum % prime == 0 {
            primeAtPower *= prime
            minimum /= prime
        } else {
            goOn = false
        }
        goOn = goOn && minimum > 1
    }
    while goOn
    possibleDivisors.append(primeAtPower)
}
    
var gcd = 1 // Initialize
for divisor in possibleDivisors {
    var possibleDivisor = true
    for val in arr where possibleDivisor {
        if val % divisor != 0 { possibleDivisor = false }
    }
    // 4. If common divisor, gcd includes it
    if possibleDivisor { gcd *= divisor }
}
print("gcd of \(arr) is", gcd)

Yields

gcd of [4, 8, 12] is 4

Thank you, very much. Even though it's kind of long. I'm gonna have to undersand some of the approaches you used but I will gladly do that. — Ali Abraham, Aug 03 '20 at 07:29
Also thank you for the explanations throughout the code. It helps a lot!!! — Ali Abraham, Aug 03 '20 at 07:29
I looked a bit more. There is an error in comment: that would test numbers upto 100, not 10000. And you could add a test before append : if primeAtPower > 1 { possibleDivisors.append(primeAtPower) } — claude31, Aug 03 '20 at 08:38

for loop to check if a number in array divides all elements in array

1 Answers1