/*
  Author:  Pate Williams (c) 1997

  "Exercise 1.2. A computer program for phi(x, a).
  Write a function phi(x, a), covering a <= 10,
  following the idea mentioned above. Incorporate
  this function in a computer program which reads
  x and a and prints phi(x, a)." -Hans Riesel-
  See "Prime Numbers and Computer Methods for
  Factorization" by Hans Riesel second edition
  pages 17-18.
*/

#include <math.h>
#include <stdio.h>

#define A 5
#define MA 2310
#define MA2 1155
#define LENGTH 1155
#define PHIMA 480
#define BITS_PER_LONG   32
#define BITS_PER_LONG_1 31
#define SIZE 8192

long prime[A] = {2, 3, 5, 7, 11};
long sieve[SIZE] = {0}, table[SIZE] = {0};

long get_bit(long i, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;

  return (sieve[c] >> (BITS_PER_LONG_1 - b)) & 1;
}

void set_bit(long i, long v, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;
  long mask = 1 << (BITS_PER_LONG_1 - b);

  if (v == 1)
    sieve[c] |= mask;
  else
    sieve[c] &= ~mask;
}

void init_table(void)
{
  long i, j, p, s = 0;

  for (i = 2; i <= LENGTH; i++)
    set_bit(i, i & 1, sieve);
  for (i = 0; i < A; i++) {
    p = prime[i];
    j = p;
    while (j <= LENGTH) {
      set_bit(j, 0, sieve);
      j += p;
    }
  }
  set_bit(1, 1, sieve);
  for (i = 1; i <= LENGTH; i++) {
    if (get_bit(i, sieve)) table[i] = ++s;
    else table[i] = s;
  }
}

long phi5(long x)
{
  long absx = labs(x), r = absx % MA, z;

  z = (absx / MA) * PHIMA;
  if (r < MA2)
    z += table[r];
  else
    z += PHIMA - table[MA - r];
  return z * (absx / x);
}

long phi6(long x)
{
  return phi5(x) - phi5(x / 13);
}

long phi7(long x)
{
  return phi6(x) - phi6(x / 17);
}

long phi8(long x)
{
  return phi7(x) - phi7(x / 19);
}

long phi9(long x)
{
  return phi8(x) - phi8(x / 23);
}

long phi10(long x)
{
  return phi9(x) - phi9(x / 29);
}

long phi(long x, long a)
{
  if (a == 5) return phi5(x);
  if (a == 6) return phi6(x);
  if (a == 7) return phi7(x);
  if (a == 8) return phi8(x);
  if (a == 9) return phi9(x);
  return phi10(x);
}

int main(void)
{
  long a, x;

  printf("x = ");
  scanf("%ld", &x);
  printf("a = ");
  scanf("%ld", &a);
  init_table();
  printf("phi(%ld, %ld) = %ld\n", x, a, phi(x, a));
  return 0;
}