### constants

INF = 1 << 30

### main

loop do
  m, n = gets.split.map(&:to_i)
  break if (m | n) == 0

  cbs = gets.split.map(&:to_i).sort
  crs = gets.split.map(&:to_i).sort
  #p [cbs, crs]

  vn = m + n + 2
  st = m + n
  gl = m + n + 1

  edges = vn.times.map{vn.times.map{0}}
  nbrs = vn.times.map{[]}
  
  for i in (0...m)
    for j in (0...n)
      if cbs[i].gcd(crs[j]) > 1
        edges[i][m + j] = 1
        nbrs[i] << m + j
        nbrs[m + j] << i
      end
    end
  end

  (0...m).each{|i| edges[st][i] = 1; nbrs[st] << i}
  (0...n).each{|j| edges[m + j][gl] = 1; nbrs[m + j] << gl}

  fs = vn.times.map{vn.times.map{0}}

  loop do
    prevs = vn.times.map{nil}
    dists = vn.times.map{INF}
    dists[st] = 0
    q = [st]

    while ! q.empty?
      u = q.shift
      break if u == gl

      for v in nbrs[u]
        next if fs[u][v] == edges[u][v]
        vd = dists[u] + 1
        if dists[v] > vd
          dists[v] = vd
          prevs[v] = u
          q << v
        end
      end
    end
    break if dists[gl] >= INF
    
    path = []
    u = gl
    while prevs[u]
      path.unshift(u)
      u = prevs[u]
    end
    #p path
    
    min_c = INF
    u = st
    for v in path
      #p [u, v, edges[u][v], fs[u][v]]
      cf = edges[u][v] - fs[u][v]
      min_c = cf if min_c > cf
      u = v
    end

    u = st
    for v in path
      fs[u][v] += min_c
      fs[v][u] -= min_c
      u = v
    end
  end

  sum = 0
  (0...m).each{|i| sum += fs[st][i]}
  puts sum
end