using System;
using System.Collections.Generic;
using System.Linq;

namespace AOJ_1163
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int M = NextInt();
                int N = NextInt();

                if (M == 0 && N == 0) break;

                var B = NextInt(M);
                var R = NextInt(N);

                FordFulkerson fd = new FordFulkerson(M + N + 2);
                for (int i = 0; i < M; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (Gcd(B[i], R[j]) > 1) fd.AddEdge(i + 2, j + M + 2, 1);
                    }
                }
                for (int i = 0; i < M; i++)
                {
                    fd.AddEdge(0, i + 2, 1);
                }
                for (int i = 0; i < N; i++)
                {
                    fd.AddEdge(i + M + 2, 1, 1);
                }

                var ans = fd.MaxFlow(0, 1);

                Console.WriteLine(ans);
            }

            Console.ReadKey();
        }

        static List<string> line = new List<string>();
        static int index = 0;
        static String ReadNext()
        {
            if (line.Count <= index) line.AddRange(Console.ReadLine().Split());
            return line[index++];
        }
        static int NextInt() { return int.Parse(ReadNext()); }
        static int[] NextInt(int N) { int[] ret = new int[N]; for (int i = 0; i < N; i++) ret[i] = int.Parse(ReadNext()); return ret; }
        static long NextLong() { return long.Parse(ReadNext()); }
        static long[] NextLong(int N) { long[] ret = new long[N]; for (int i = 0; i < N; i++) ret[i] = long.Parse(ReadNext()); return ret; }


        /// <summary>
        /// 最大公約数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static int Gcd(int a, int b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
    }

    /// <summary>
    /// 最大流　容量に注意
    /// </summary>
    class FordFulkerson
    {
        public struct Edge
        {
            public int to, cap, rev;
        }

        public List<Edge>[] G;
        bool[] used;
        int INF = 1000000009;

        public FordFulkerson(int V) //頂点数
        {
            G = new List<Edge>[V].Select(x => new List<Edge>()).ToArray();
            used = new bool[V];
        }

        public void AddEdge(int from, int to, int cap)
        {
            G[from].Add(new Edge() { to = to, cap = cap, rev = G[to].Count });
            G[to].Add(new Edge() { to = from, cap = 0, rev = G[from].Count - 1 });
        }

        int Dfs(int v, int t, int f)
        {
            if (v == t)
                return f;
            used[v] = true;

            for (int i = 0; i < G[v].Count; i++)
            {
                var e = G[v][i];
                if (!used[e.to] && e.cap > 0)
                {
                    int d = Dfs(e.to, t, Math.Min(f, e.cap));
                    if (d > 0)
                    {
                        e.cap -= d;
                        G[v][i] = e;

                        var temp = G[e.to][e.rev];
                        temp.cap += d;
                        G[e.to][e.rev] = temp;

                        return d;
                    }
                }
            }
            return 0;
        }

        public int MaxFlow(int s, int t)
        {
            int flow = 0;
            while (true)
            {
                used = new bool[used.Length];
                int f = Dfs(s, t, INF);
                if (f == 0) return flow;
                flow += f;
            }
        }
    }
}



Measured memory_bytes: 45760