You don't need to be dividing up to the max but just finding the remainder upto the n/2 or sqrt of n even will do but to start off you can loop till n/2.