You only need to try the _prime_ bases up to 2 log^2(n). So the total number of bases here would be 79060.