var a:array[..]of longint;

     n,m,i,ans:longint;

 function gcd(x,y:longint):longint;

 var r:longint;

 begin

  repeat

   r:=x mod y;

   x:=y;

   y:=r;

  until r=;

  exit(x);

 end;

 function fi(x:longint):longint;

 var i:longint;

 begin

  fi:=x;

  for i:= to trunc(sqrt(x)) do

   if x mod i= then

   begin

    fi:=fi div i*(i-);

    while x mod i= do x:=x div i;

   end;

  if x> then fi:=fi div x*(x-);

 end;

 function clac(x:longint):longint;

 var i:longint;

 begin

  for i:= to m do

   if x mod gcd(n,a[i])= then exit(fi(n div x));

  exit();

 end;

 begin

  assign(input,'1.in'); reset(input);

  assign(output,'1.out'); rewrite(output);

  readln(n,m);

  for i:= to m do read(a[i]);

  for i:= to trunc(sqrt(n)) do

   if n mod i= then

   begin

    ans:=ans+clac(i);

    if i*i<>n then ans:=ans+clac(n div i);

   end;

  writeln(n-ans);

  close(input);

  close(output);

 end.