Integer Overflow

Yesterday i was working on a problem where we have to check a number is whether prime or not , for that i gone through two famous prime testing algorithm , but i was getting wrong answer , i was trying hard but nothing worked , then i searched on internet , where i found very interesting thing.

It is well known that when we have to find the value of a raise to power n , we can calculate it in O ( log n ) time , we can apply same logic when we have to get a * b, what ever we did to n same thing we do to b here. This was the culprit as when i was calculating a * b it was going beyond integer range ( Actually we apply this logic when we have to found modulo of a * b otherwise it is of no use because it will grow beyond longest integer value ).

But above logic won't work if 2 * a goes beyond longest integer range, java provide us with facility to create our own custom integer .