CODEWITHSUNDEEP
algorithmlistmathnumbers
Flamy
Flamy

Reputation: 313

Find the smallest whole number that is a factor of all numbers in a list

Is there a way to find the Greatest Common Divisor of N numbers from a list.

for example: there is a list like 4,24,64,80,40,1264 and so on... I want a method with which i could find the Greatest Common Divisor in the list. In the above case it is 4 which is the Greatest Common Divisor. What i want is a dynamic solution that works on a list and gives the value. (A whole number that divides all the numbers of the list without giving a reminder)

The solution can be in any language, C# preferably (taking advantage of Linq).

PS: Sorry if you think this belongs to math.stackexchange.com, I was actually confused between which of these to post to.

EDIT: sorry for my ignorance that i used LCD initially.

Upvotes: 0

Views: 1315

Answers (5)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Do the following :-

  1. Find the smallest number S in the list.
  2. find all prime divisors of S.
  3. for each prime pi find xi=minimum(k1,k2,k3,...) where ki is power of pi in number arr[i]
  4. GCD = x1*x2*..xk

Note: you can stop at any iteration in 3. when ki = 1 because it will be minimum.

Java Implementation : - 

public static long lgcd(long[] arr) {

        long min = arr[0];

        for(int i=0;i<arr.length;i++) {
            if(min>arr[i]) {
                min = arr[i];
            }
        }

        ArrayList div_primes = new ArrayList();
        boolean isPrime[] = new boolean[(int)Math.sqrt(min)+1];
        for(int i=0;i<isPrime.length;i++)
            isPrime[i] = true;

        for(int j=2;j<isPrime.length;j++) {
            if(isPrime[j]) {
                int x = 2*j;
                if(min%j==0) {
                    div_primes.add(j);
                } 
                for(;x<isPrime.length;x=x+j) {
                    isPrime[x] = false;
                }
            }
        }

        if(div_primes.size()<1) {
           div_primes.add(min);
        }

        long gcd = 1;

        for(int i=0;i<div_primes.size();i++) {
            long curr = (Integer)div_primes.get(i);
            long x = min;
            for(int j=0;j<arr.length;j++) {
                long acc = arr[j];
                long fact = 1;
                while(acc>1&&acc%curr==0) {
                    acc = acc/curr;
                    fact = fact*curr;
                }
                x = Math.min(x,fact);
                if(fact==1)
                    break;
            }
            gcd = gcd*x;
        }
        return(gcd);
    }

Time Complexity:

  1. primes are calculated in O(sqrt(S))
  2. total primes divisors are O(log(S))
  3. GCD calculation:- O(log(S)*N)

Edit: Forget to add corner case where the minimum number itself is prime so added following code 

if(div_primes.size()<1){
            div_primes.add(min);
        }

Upvotes: 1

Timothy Shields
Timothy Shields

Reputation: 79531

The least common multiple function (LCM) is associative and commutative. So you can compute the LCM of an array A of n numbers by simply doing the following.

k = 1
for i = 1..n
    k = LCM(k, A[i])

There are existing algorithms for LCM. See here: http://en.m.wikipedia.org/wiki/Least_common_multiple

Upvotes: 3

Gangnus
Gangnus

Reputation: 24484

Both GCD and LCM are computed so:

  • resolve in primes each elements of the list. As 60=2^2*3*5. Write down these prime representation as vectors. As 60=(2,1,1,0,0,..)
  • For GCD find minimum for the same position in all representations. Repeat for all positions.
  • For LCM it will be maximum.
  • Turn back these representations to primes and mutliply them back.

As I remember, it is the program of 6th grade at the school. (for 12 years - old children)

Upvotes: 0

Joe Liu
Joe Liu

Reputation: 61

I think what you want is Greatest Common Divisor(GCD) instead of Least Common Multiple(LCM). The GCD and LCM of your example should be 4 and 75840 respectively.

You can get the GCD and LCM of a list of numbers by prime factorization. It can de coded as a dynamic solution (by recording the minimum and maximum exponent of each prime factor). Take your list as an example:

4 = 2^2
24 = 2^3 * 3
64 = 2^6
80 = 2^4 * 5
40 = 2^3 * 5
1264 = 2^4 * 79

So the GCD is 2^2 = 4 and the LCM is 2^6 * 3 * 5 * 79 = 75840.

Upvotes: 1

smn_onrocks
smn_onrocks

Reputation: 1342

You can do this simply short the list and ten run a loop that will access each value and divide all others value in your list in a inner loop increment a counter after each successful division and then compare previous count with current outside of the inner loop then if current count is smaller the store the actual value. hope this could solve your problem

Upvotes: 0

Related Questions