/*******************************************************************
   ArmBob program to calculate the number of irreducible
   Gaussian integers with norm less than or equal to n.
   You can get ArmBob from
        ftp://micros.hensa.ac.uk/micros/arch/riscos/b/b178
    or from my web page (vide infra).

   Sample runs:
          Enter a positive integer > 1 : 100
          The number of irreducible Gaussian integers
           with norm <= 100 is 4928 .

          Enter a positive integer > 1 : 1000
          The number of irreducible Gaussian integers
           with norm <= 1000 is 313752 .

   G.C.Wraith       13/2/98
 

          http://www.wraith.u-net.com/

*********************************************************************/

main()
{ local n;
 repeat { print("Enter a positive integer > 1 : ");
               n = val(input());} until (n > 1) ;
 print("The number of irreducible Gaussian integers\n",
       " with norm <= ",n," is ",
       4            /* for norm sqrt(2), i.e. 1+i, 1-i, -1-i, -1+i  */
       + 4*f(3,n)   /* for p,-p,ip,-ip, with p mod 4 = 3, p prime */
       + 8*f(5,n*n) /* for a+ib, a-ib, -a+ib,-a-ib, b+ia, b-ia, -b-ia, -b+ia, 
                        where a*a+b*b is an odd prime */
       ," .\n");
} 

/* returns the number of odd primes congruent to x mod 4 
    less than or equal to max */
f(x,max)
{
 local count;
 count = 0;
 while (x <= max)
   {
     if (isprime(x)) count++;
     x += 4; 
   }
 return count;
}

isprime(x) /* crass but simple - x has to be odd */
{
 local d,ok;
 ok = 1; d = 3;
 while ( d*d <= x && (ok = (x%d != 0))) d += 2;
 return ok;
}
