import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer

object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val Array(m, n) = readLine.trim.split(' ').map(_.toInt)
    if (m == 0) return
    val blue = readWhile(m)
    val red = readWhile(n)
    println(new Dinic(m, n, blue.indices.flatMap{i ⇒ red.indices.withFilter(j ⇒ gcd(blue(i), red(j)) != 1).map{j ⇒ (i, j)}}.toArray).calMaxMatching)
    solve
  }
  def readWhile(n: Int): Array[Int] = {
    var count = n
    var result = Nil: List[Array[Int]]
    while (count > 0){
      val line = readLine.trim.split(' ').map(_.toInt)
      count -= line.length
      result ::= line
    }
    result.flatten.toArray
  }

  implicit class Extend[T](value: T){
    def also(func: T ⇒ Unit): T = {func(value); value}
    def let[A](func: T ⇒ A): A = func(value)
  }
  def gcd(a: Int, b: Int): Int = {
    b match {
      case 0 ⇒ a
      case _ ⇒ gcd(b, a % b)
    }
  }
  def maxMatching(s: Int, t: Int, edges: Array[(Int, Int)]): Int = {
    new Dinic(s, t, edges).calMaxMatching
  }
  private class Dinic(s: Int, t: Int, edges: Array[(Int, Int)]) {
    val edge = Array.tabulate(s + t + 2){_ ⇒ ArrayBuffer[(Int, Int, Boolean)]()}
    for (x ← 1 to s){
      edge(x).append((0, edge(0).length, false))
      edge(0).append((x, 0, true))
    }
    for (y ← (s + 1) to s + t){
      edge(y).append((s + t + 1, edge(s + t + 1).length, true))
      edge(s + t + 1).append((y, 0, false))
    }
    edges.foreach{
      case (from, to) ⇒
        edge(from + 1).append((to + s + 1, edge(to + s + 1).length, true))
        edge(to + s + 1).append((from + 1, edge(from + 1).length - 1, false))
    }
    val levels = Array.tabulate(s + t + 2){_ ⇒ -1}
    val dfsLast = Array.tabulate(s + t + 2){_ ⇒ 0}
    def bfs: Unit = {
      dfsLast.indices.foreach(i ⇒ dfsLast(i) = 0)
      levels.indices.foreach(i ⇒ levels(i) = -1)
      levels(0) = 0
      val queue : mutable.Queue[Int]= mutable.Queue()
      queue.enqueue(0)
      while(queue.nonEmpty){
        val top = queue.dequeue()
        for ((to, _, b) ← edge(top) if b && levels(to) == -1) {
          levels(to) = levels(top) + 1
          queue.enqueue(to)
        }
      }
    }
    def dfs(from: Int): Boolean= {
      if (from == s + t + 1) true
      else {
        var makePath = false
        for (i ← dfsLast(from) until edge(from).length if  !makePath && edge(from)(i)._3) {
          dfsLast(from) = i
          val (to, j, _) = edge(from)(i)
          if (levels(to) > levels(from) && dfs(to)) {
            edge(from)(i) = (to, j, false)
            edge(to)(j) = (from, i, true)
            dfsLast(from) += 1
            makePath = true
          }
        }
        makePath
      }
    }
    def calMaxMatching: Int = {
      var count = 0
      var canMatch = true
      while (canMatch){
        canMatch = false
        bfs
        if (levels.last != -1) {
          canMatch = true
          while (dfs(0)) {
            count += 1
          }
        }
      }
      count
    }
  }
}
