require 'prime'

module Graphical
	require 'set'

	def get_path_by_dfs(s, t, reached = Set.new)
		reached << s
		return [] if s == t
		s.out_edges.each{|e|
			v = e.to
			next if reached.include?(v)
			path = get_path_by_dfs(v, t, reached) 
			return [e] + path if path
		}
		nil
	end
end

class Graph
	include Graphical

	def initialize(*options)
		@options = Set[*options]
	end

	def add_node(property = {})
		Node.new(property)
	end

	def add_edge(u, v, property = {})
		e = Edge.new(u, v, property)
		u.add_edge(e)
		v.add_edge(e)
		e
	end
	
	def del_edge(e)
		u, v = e.opposite.keys
		u.del_edge(e)
		v.del_edge(e)
		e
	end

	class Node
		def initialize(property)
			@property = property
			@edges = Set.new
		end

		def add_edge(e)
			@edges << e
		end

		def del_edge(e)
			@edges.delete(e)
		end

		def to_s
			@property[:name] || super
		end

		def each_edge
			@edges.each{|e| 
				yield e
			}
		end

		attr_reader :property
	end

	class Edge
		def initialize(u, v, property)
			@opposite = {u => v, v => u}
			@property = property
		end
		attr_reader :opposite, :property

		def to_s
			@property[:name] || super
		end

		def length
			@property[:length] || 1
		end
	end

	def each_out_connection_of(u)
		u.each_edge{|e|
			yield(e.opposite[u], e.length)
		}
	end

	alias :each_in_connection_of :each_out_connection_of
end

class Digraph < Graph
	def add_node(property = {})
		Node.new(property)
	end

	def add_edge(u, v, property = {})
		e = Edge.new(u, v, property)
		u.add_out_edge(e)
		v.add_in_edge(e)
		e
	end
	
	def del_edge(e)
		u, v = e.from, e.to
		u.out_edges.delete(e)
		v.in_edges.delete(e)
		e
	end

	class Node < Graph::Node
		def initialize(property)
			@property = property
			@out_edges = Set.new
			@in_edges = Set.new
		end

		def add_out_edge(e)
			@out_edges << e
		end

		def del_out_edge(e)
			@out_edges.delete(e)
		end

		def add_in_edge(e)
			@in_edges << e
		end

		def del_in_edge(e)
			@in_edges.delete(e)
		end

		attr_reader :in_edges, :out_edges
	end

	class Edge < Graph::Edge
		def initialize(u, v, property)
			@from = u	
			@to = v
			@property = property
		end

		attr_reader :from, :to
	end

	def each_out_connection_of(u)
		u.out_edges.each{|e|
			yield [e.to, e.length]
		}
	end

	def each_in_connection_of(v)
		v.in_edges.each{|e|
			yield [e.from, e.length]
		}
	end

#----------------------------------------------------------

	def get_path_bfs(s, t)
		path_edge = {}
		reached = Set[s]
		queue = [s]
		while !queue.empty? 
			u = queue.shift
			u.outgoings.each{|e|
				v = e.to
				next if reached.include?(v)	
				reached << v
				queue << v
				path_edge[v] = e

				if v == t
					path = []
					while e = path_edge[v]
						path.unshift e
						v = e.from
					end
					return path
				end
			}
		end	
		return nil
	end

	def get_path_dfs(s, t, reached = Set.new)
		reached << s	
		s.outgoings.each{|e|
			v = e.to
			next if reached.include?(v)
			return [e] if v == t
			
			path = get_path_dfs(v, t, reached) 
			return [e] + path if path
		}
		nil
	end

end

loop {
	n, m = gets.split.map &:to_i
	break if n == 0

	a = gets.split.map &:to_i
	b = gets.split.map &:to_i

	g = Digraph.new
	left_nodes = a.map{|x|
		g.add_node({:facts => Prime.prime_division(x).map(&:first)})
	}
	right_nodes = b.map{|x|
		g.add_node({:facts => Prime.prime_division(x).map(&:first)})
	}

	left_nodes.each{|u|
		right_nodes.each{|v|
			g.add_edge(u, v) unless (u.property[:facts] & v.property[:facts]).empty?
		}
	}

	s = g.add_node
	t = g.add_node

	left_nodes.each{|v| g.add_edge(s, v)}	
	right_nodes.each{|v| g.add_edge(v, t)}	
	
	c = 0
	while path = g.get_path_by_dfs(s, t)
		c += 1
		path.each{|e|
			g.del_edge(e)
			g.add_edge(e.to, e.from)
		}
	end
	p c
}