Hello, StatujaLeha, you wrote: a C>> the Formula for upper bound minFactorial (p, e) very strange, p ** sqrt (2*e) it nevertheless is normal much more, than p*e, SL> Yes, it not simply strange, but incorrect Well probably it is impossible to tell that it incorrect if provides the correct result Actually true will be any formula on which the result turns out not less that minimum number, you, probably, provides it. SL> the idea was such: if at us it is set m to count a level e from which idle time p enters in m!, we should use the known formula. SL> this formula such that has races in points, multiple p. Therefore we search minimum q such that (p ** q)! % (p ** e) == 0, and we go downwards steps in the size p further. SL> Replaced the formula on qMin = int (ceil (log (e * (p - 1) + 1, p))), became faster: http://ideone.com/22C4V6 SL> But the variant with x = p*e is all the same better: http://ideone.com/vmy6tN That is took the maximum boundary approximately e * (p - 1) + 1, but approximated upwards to a number level p. I in any way will not understand, what for to approximate to a level? Abundantly clear that (e*p)! % (p ** e) == 0 (in that factorial is exactly e the factors sharing on p). On the other hand, that known formula is a geometrical progression in which from each member its integer part, therefore its total of strictly less total "not cut off" which it is equal x / (p - 1) is taken. Total we received a segment [e * (p - 1) + 1; e * p] on which certainly lies our optimal x. As minimum x, obviously, it is multiple p (in a factorial the last factor should bring a victory), them and it is necessary to sort out, from any end. As the left boundary corresponds in a type e * p - e + 1, and the right boundary e * p is multiple p it is obvious that at e <= p (the most frequent case) on this segment lies exactly one number, multiple p - its right boundary, therefore checkFactorial it is possible not to calculate at all. That is, apparently, it is necessary to approximate to multiple, instead of to a level though (positive) the level is too multiple And though you approximate lower bound, and the total name upper, but calculation shows that this number will be valid upper bound, though probably and enough far (1481124 misses for a segment from 23M to 24M). Rescues only that for e=1 (the main case) the formula (without the registration of errors) gives exactly p (as well as previous But here if log (p, p) it appears hardly more , it is necessary to transverse p variants. And here for e=2 both give p^2 instead of 2*p, that is for such numbers, and approximately sqrt (N)/log (sqrt (N)), it is necessary to transverse them approximately p superfluous variants, that is all approximately N/log (N) that practically explains excess. SL> the idea was in spending storage and to receive from it a profit. I.e. 2400000 int gets into storage, therefore we take and we are not soared about storage. Well, received constant (multiplyings against divisions) a profit in comparison with factorization of each number by means of a sieve. There is a question how to optimize further when storages already begins for all numbers to N, but a tested segment [M; N] still gets into storage. For sieves on still gave me storage for N=240M, but for N=2.4G - already hardly. And small modification of your approach can help, about it I and wrote. Basically, even if [M; N] does not get into storage, it can be broken on slightly getting and to turn with everyone this focus. And the sieve turns out semibit instead of . It is a pity only that to divisions instead of multiplyings to pass, probably, it is necessary. And yes, PyPy is slightly