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.