# PROBLEM LINK

# DIFFICULTY

SIMPLE

# PREREQUISITES

Simple Math

# PROBLEM

You are given a list of numbers. You have to find the smalelst number which divides all these numbers.

# QUICK EXPLANATION

To the initiated, this question should be a breeze.

- Find the
**GCD**of the list of numbers. - Find the
**smallest prime factor**of the GCD.

# EXPLANATION

The **GCD** of two numbers can be found using the **Euclid’s Algorithm**.

gcd(a,b) return (b == 0) ? a : gcd(b, (a mod b))

The **GCD** of a list of numbers **A[1 … N]** can be found as

let G = 0 for i = 1 to N G = gcd( A[i], G )

The above is intuitive and easy to prove by induction.

Now, the next step is to find the **smallest prime factor** of the **GCD**. Calculating this can be done in **O(sqrt(N))** time easily.

for i = 2 to floor(sqrt(G)) if G is divisible by i return i return G // Since G is prime!

This calculation is probably the most time consuming step in the solution. Although, iterating till **sqrt**(G) will fit within the time limit, you can make one optimization to make it faster. That optimization is **pre-calculation**! You can pre-calculate the smallest primes in the factorization of any number by **sieving**.

Consider the snippet below

smallestPrime[ 2 ... N ] // We will store our answers here for i = 2 to N smallestPrime[i] = i for i = 2 to N if smallestPrime[i] = i for j = 2*i to N, step-size i smallestPrime[j] = min( smallestPrime[j], i )

Notice how we modify the step in which in the usual **Sieve of Eratosthenes**, we set the **multiples of i** as **non-prime**. In this step now, we are simply updating the **smallestPrime** array at index **j**. This is a very clever trick to master while solving problems. When you deal with a problem where you need to perform an operation based on **all prime factors** of a number (like in this case, we wanted to find the smallest of them), a small code snippet like above is usually needed.

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.