Два числа называются взаимно простыми, если они не имеют общего натурального делителя,...

Question

Два числа называются взаимно простыми, если они не имеют общего натурального делителя, кроме 1. Иными словами, их наибольший общий делитель равен 1.
Найдите количество шестизначных чисел, взаимно простых с числом 70.

Answer 1

Var j,n : Longint;

Function Check(a,b : Longint) : Boolean;
Var i : Longint;
Begin
  Check:=True;
  For i:=2 to b do If ((a mod i)=0) and ((b mod i)=0) then Check:=False;
end;

Begin
  n:=0;
  For j:=100000 to 999999 do If Check(j,70) then Inc(n);
  Writeln(n);
end.