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[] a = new int[A];
            int[] b = new int[B];
            for (int i = 0; i < A; i++) { a[i] = read.NextInt(); }
            for (int i = 0; i < B; i++) { b[i] = read.NextInt(); }

            int S = A + B;
            List<Edge>[] edges = Enumerable.Range(0, S + 2).Select(i => new List<Edge>()).ToArray();
            for (int i = 0; i < A; i++) { Edge.Add(edges, S, i, 1); }
            for (int i = 0; i < B; i++) { Edge.Add(edges, 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(edges, i, A + j, 1);
                    }
                }
            }

            int ans = new MaxFlow().Run(edges, 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 MaxFlow
    {
        readonly int INF = (int)1e9;
        List<Edge>[] Edges;
        int T;
        bool[] used;

        public int Run(List<Edge>[] edges, int s, int t)
        {
            Edges = edges;
            T = t;
            int res = 0;
            while (true)
            {
                used = new bool[Edges.Length];
                int f = DFS(s, INF);
                if (f == 0) return res;
                res += f;
            }
        }

        int DFS(int v, int flow)
        {
            if (v == T) return flow;
            used[v] = true;
            for (int i = 0; i < Edges[v].Count; i++)
            {
                Edge e = Edges[v][i];
                if (!used[e.to] && e.capacity > 0)
                {
                    int d = DFS(e.to, Math.Min(flow, e.capacity));
                    if (d > 0)
                    {
                        e.capacity -= d;
                        Edges[e.to][e.reverse].capacity += d;
                        return d;
                    }
                }
            }
            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: 26472