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

class Program
{
    static void Main(string[] args)
    {
        Read read = new Read();
        string s;

        while ((s = Console.ReadLine()) != "0 0")
        {
            int[] t = Array.ConvertAll(s.Split(), int.Parse);
            int A = t[0];
            int B = t[1];
            int S = A + B;
            int[] a = new int[A];
            int[] b = new int[B];
            var G = Enumerable.Range(0, S + 2).Select(i => new List<Edge>()).ToArray();
            for (int i = 0; i < A; i++) { a[i] = read.NextInt(); Edge.Add(G, S, i, 1); }
            for (int i = 0; i < B; i++) { b[i] = read.NextInt(); Edge.Add(G, A + i, S + 1, 1); }

            for (int i = 0; i < A; i++)
            {
                for (int j = 0; j < B; j++)
                {
                    if (GCD(a[i], b[j]) > 1)
                    {
                        Edge.Add(G, i, A + j, 1);
                    }
                }
            }
            int ans = new Dinic(G).MaxFlow(S, S + 1);
            Console.WriteLine(ans);
        }

        Console.ReadLine();
    }

    static long GCD(long i, long j)
    {
        while (j != 0) { long t = i % j; i = j; j = t; }
        return i;
    }

    class Edge
    {
        public int to, capacity, reverse;
        public Edge(int to, int capacity, int reverse)
        {
            this.to = to;
            this.capacity = capacity;
            this.reverse = reverse;
        }
        public static void Add(List<Edge>[] Edges, int from, int to, int capacity)
        {
            Edges[from].Add(new Edge(to, capacity, Edges[to].Count));
            Edges[to].Add(new Edge(from, 0, Edges[from].Count - 1));
        }
    }

    class Dinic
    {
        readonly int INF = (int)1e9;
        List<Edge>[] G;
        int[] level;
        int[] iter;

        public Dinic(List<Edge>[] G)
        {
            this.G = G;
        }

        public int MaxFlow(int s, int t)
        {
            int flow = 0;
            while (true)
            {
                BFS(s);
                if (level[t] < 0) return flow;
                iter = new int[G.Length];
                int f;
                while ((f = DFS(s, t, INF)) > 0) { flow += f; }
            }
        }

        private void BFS(int s)
        {
            level = Enumerable.Repeat(-1, G.Length).ToArray();
            Queue<int> que = new Queue<int>();
            que.Enqueue(s);
            level[s] = 0;
            while (que.Count > 0)
            {
                int v = que.Dequeue();
                foreach (Edge e in G[v].Where(e => e.capacity > 0 && level[e.to] < 0))
                {
                    level[e.to] = level[v] + 1;
                    que.Enqueue(e.to);
                }
            }
        }

        private int DFS(int v, int t, int flow)
        {
            if (v == t) return flow;
            while (iter[v] < G[v].Count)
            {
                Edge e = G[v][iter[v]];
                if (e.capacity > 0 && level[v] < level[e.to])
                {
                    int d = DFS(e.to, t, Math.Min(flow, e.capacity));
                    if (d > 0)
                    {
                        e.capacity -= d;
                        G[e.to][e.reverse].capacity += d;
                        return d;
                    }
                }
                iter[v]++;
            }
            return 0;
        }
    }

    class Read
    {
        Queue<string> que = new Queue<string>();
        
        public int NextInt()
        {
            if (que.Count == 0) { Enqueue(); }
            return int.Parse(que.Dequeue());
        }

        private void Enqueue()
        {
            foreach (string s in Console.ReadLine().Split())
            {
                que.Enqueue(s);
            }
        }
    }
}

Measured memory_bytes: 26536