/*
  Author:  Pate Williams (c) 1997

  "Exercise 5.1 Trial division.
  Explore the practical upper limit of N for the
  program TrialDivision above when used on your
  computer. (It is for primes that the longest
  running times occur.) Plot the maximal running
  time vs. the size of N in a logarithmic diagram.
  Decide on a value of G in order to obtain
  reasonable running times even in the case when
  N happens to be a product of nearly equal prime
  factors." -Hans Riesel-
  See "Prime Numbers and Computer Methods for
  Factorization" by Hans Riesel second edition
  page 145.
*/

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

void reduce(long G, long r, long *factor,
            long *m, long *plimit)
{
  if (r > 1) {
    while (*m % r == 0) {
      *m /= r;
      factor[0]++;
      factor[factor[0]] = r;
    }
  }
  *plimit = sqrt(*m) + 0.5;
  if (*plimit > G) *plimit = G;
}

void divide(long G, long n, long *factor, long *m)
{
  long p = 5, plimit;

  factor[0] = 0;
  *m = n;
  reduce(G, 2, factor, m, &plimit);
  if (*m == 1) return;
  reduce(G, 3, factor, m, &plimit);
  if (*m == 1) return;
  while (p <= plimit) {
    if (*m % p == 0)
      reduce(G, p, factor, m, &plimit);
    if (*m == 1) return;
    p += 2;
    if (*m % p == 0)
      reduce(G, p, factor, m, &plimit);
    if (*m == 1) return;
    p += 4;
  }
  if (p > sqrt(*m) + 0.5)
    reduce(G, *m, factor, m, &plimit);
}

int main(void)
{
  long G = 65537l, b = 16, i, n, x, m;
  long delta = 8192, hi = 1024 * 65536l, lo = 65536l;
  long factor[2048];
  clock_t time0, time1;

  n = lo;
  while (n <= hi) {
    time0 = clock();
    for (i = 0, x = n; i < delta; i++, x++)
      divide(G, x, factor, &m);
    time1 = clock() - time0;
    n *= 2;
    printf("%ld %ld\n", b++, time1);
  }
  return 0;
}