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

long countPrimes(long unsigned int n);

int main() {
	long unsigned int i;
	double maxDiv = 0;
	for (i = 3; i <= 1000000; i++) {
	    long tot = countPrimes(i);
		double div = i / (double)(tot);
		if (div > maxDiv) {
		  printf("Found new max: %lu / %lu = %f\n",i,tot,div);
		  maxDiv = div;
		}
		if (i % 100000 == 0)
			printf("On %lu\n",i);
	}
}

long countPrimes(long unsigned int n) {
  long unsigned int j,q,c = n - 1;
  int found[n];
  for (j = 0; j < n; j++)
	found[j] = 0;
  
  for (j = 2; j < sqrt(n); j++) {
    if (n % j == 0) {
	  for (q = j; q < n; q += j) {
	    if (found[q-1] != 1) {
	      found[q-1] = 1;
	      c -= 1;
		}
	  }
	}
  }
  return c;
}