/*
  Author:  Pate Williams (c) 1997

  "Exercise 5.2. Statistics on prime factors.
  Collect some statistics on the size of the
  prime factors p of large numbers N by
  counting the number of cases for which
  ln ln p falls in various intervals of length
  0.2, e.g. 0.2k < ln ln p < 0.2(k + 1),
  k = 1, 2, 3,..., 10." -Hans Riesel-
  See "Prime Numbers and Computer Methods for
  Factorization" by Hans Riesel second edition
  page 161.
*/

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

#define BITS_PER_LONG   32
#define BITS_PER_LONG_1 31
#define MAX_SIEVE 500000l
#define PRIME_SIZE 41538l
#define SIEVE_SIZE (MAX_SIEVE / BITS_PER_LONG + 1)

struct factor {long expon, prime;};

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 Sieve(long n, long *sieve)
{
  long c, i, inc;

  set_bit(0, 0, sieve);
  set_bit(1, 0, sieve);
  set_bit(2, 1, sieve);
  for (i = 3; i <= n; i++)
    set_bit(i, i & 1, sieve);
  c = 3;
  do {
    i = c * c, inc = c + c;
    while (i <= n) {
      set_bit(i, 0, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, sieve)) c++;
  } while (c * c <= n);
}

int trial_division(long *N, long *prime,
                   struct factor *f, long *count)
{
  int found;
  long B, d, e, i, j = 0, k, l, m, n, r;
  long t[8] = {6, 4, 2, 4, 2, 4, 6, 2};
  long table[8] = {1, 7, 11, 13, 17, 19, 23, 29};

  if (*N <= 5) {
    *count = 1;
    f[0].expon = 1;
    switch (*N) {
      case 1 : f[0].prime = 1; break;
      case 2 : f[0].prime = 2; break;
      case 3 : f[0].prime = 3; break;
      case 4 : f[0].expon = 2; f[0].prime = 2; break;
      case 5 : f[0].prime = 5; break;
    }
    return 1;
  }
  *count = 0;
  B = prime[PRIME_SIZE - 1];
  i = - 1, l = sqrt(*N), m = - 1;
  L2:
  m++;
  if (i == PRIME_SIZE) {
    i = j - 1;
    goto L5;
  }
  d = prime[m];
  k = d % 30;
  found = 0;
  for (n = 0; !found && n < 8; n++) {
    found = k == table[n];
    if (found) j = n;
  }
  L3:
  r = *N % d;
  if (r == 0) {
    e = 0;
    do {
      e++;
      *N /= d;
    } while (*N % d == 0);
    f[*count].expon = e;
    f[*count].prime = d;
    *count = *count + 1;
    if (*N == 1) return 1;
    goto L2;
  }
  if (d >= l) {
    if (*N > 1) {
      f[*count].expon = 1;
      f[*count].prime = *N;
      *count = *count + 1;
      return 1;
    }
  }
  else if (i < 0) goto L2;
  L5:
  i = (i + 1) % 8;
  d = d + t[i];
  if (d > B) return 0;
  goto L3;
}

int main(void)
{
  double x;
  long e = 6, N, i, j, n, p = 2;
  long prime[PRIME_SIZE], sieve[SIEVE_SIZE], s[10] = {0};
  struct factor f[32];

  Sieve(MAX_SIEVE, sieve);
  for (i = 0; i < PRIME_SIZE; i++) {
    while (!get_bit(p, sieve)) p++;
    prime[i] = p++;
  }
  for (i = 0; i < 3; i++) {
    n = pow(10, e++);
    for (j = 0; j < 1000; j++) {
      N = n + j;
      trial_division(&N, prime, f, &p);
      if (p != 1) {
        x = log(log(p));
        if (x > 0.2 && x < 0.4) s[0]++;
        else if (x > 0.4 && x < 0.6) s[1]++;
        else if (x > 0.6 && x < 0.8) s[2]++;
        else if (x > 0.8 && x < 1.0) s[3]++;
        else if (x > 1.0 && x < 1.2) s[4]++;
        else if (x > 1.2 && x < 1.4) s[5]++;
        else if (x > 1.4 && x < 1.6) s[6]++;
        else if (x > 1.6 && x < 1.8) s[7]++;
        else if (x > 1.8 && x < 2.0) s[8]++;
        else if (x > 2.0 && x < 2.2) s[9]++;
      }
    }
  }
  for (i = 0; i < 10; i++)
    printf("%ld\n", s[i]);
  return 0;
}