week9 prog assig1

import sys
import os
import math
if not os.environ.get("ONLINE_JUDGE"):
    sys.stdin = open('./in.txt', 'r')
    sys.stdout = open('./out.txt', 'w')

# rather than looping across all number max(a,b) we can use the foll. Euler's formula
# gcd(a,b)=gcd(b,a%b) where b!=0
# gcd(a,0)=a


def gcd(a, b):
    r = 0
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

# prime factors are the small possible units that can divide a number


def prime_factor_count(n):
    count = 0
    # finding the number of twos that can divide n, as 2 is the only even prime numbe
    while n % 2 == 0:
        count += 1
        n /= 2
    # now that div by 2 is done, the n must be odd now
    # and 1 is not prime, and 2 is covered, so we start at 3
    i = 3

    # for any factors it is okay if we go only till sqrt(n)
    while i < math.sqrt(n):
        # check if n is divisible by i as many times as possible and update the count
        # this is because we need the prime factors
        # like 27=3*3*3
        while n % i == 0:
            count += 1
            n /= i
        i += 2

    # finally if any residue is present in n, it must be prime, beacuse we have divided by 2, and all other ints below sqrt(n), so we add that to the count too
    if n > 2:
        count += 1
    return count


n, m = map(int, input().split())

a = [0]
a += list(map(int, input().split()))

pairs = []
for _ in range(m):
    pairs.append(list(map(int, input().split())))
# print(pairs)
# print(a)

div_count = 0
for pair in pairs:
    # find max number that can divide the pair
    divisor = gcd(a[pair[0]], a[pair[1]])
    # if n,m are coprime like gcd(5,9)=1, division by 1 is meaningless in our scenario, so omitting it
    if divisor > 1:
        # add the max number of times the pair can be divided
        div_count += prime_factor_count(divisor)
        # update the list value
        a[pair[0]] /= divisor
        a[pair[1]] /= divisor
print(div_count)