How to find perfect squares in a range efficiently when inputs are large numbers in Python
The question is how to efficiently find perfect squares within a given range when the inputs are very large numbers. My solution is giving an error Time Limit Exceeded
. I have already checked the following links, but they did not solve my problem:
- Python program in Perfect Squares
- How can I check if a number is a perfect square?
- Fastest way to determine if the square root of an integer is an integer (I don't know how to implement the solution given in this link in Python).
Problematic question:
Input format: the first line contains T, the number of checks. T, each on a new line. Each test file contains two spaces, separated by a space, representing A and B. Find all perfect squares in the range A and B (both inclusive).
Input example:
2 3 9 17 24
The code I wrote is:
import math
def is_perfect_square(n):
return n % n**0.5 == 0
t = int(raw_input())
for i in range(t):
numbers = map(int, raw_input().split())
count = 0
for j in xrange(numbers[0], numbers[1] + 1): # I also tried range() which gave memory error
if (is_perfect_square(j)):
count = count + 1
print count
While this code works for smaller numbers, it gives an error Time Limit Exceeded
for large inputs.
(NOTE: gmpy
not an option as the code needs to be run in an online compiler that doesn't have a module gmpy
)
source to share
Instead of going through from A
to B
and checking for perfect squares, why not just cross out the whole numbers from sqrt(A)
to sqrt(B)
and square them to give you your answer.
For example, find square numbers between 1000 and 2000:
sqrt(1000) = 31.6 --> 32 (need the ceiling here)
sqrt(2000) = 44.7 --> 44 (need the floor here)
So our answer is:
32 2 = 1024 33 2 = 1089 34 2 = 1156 35 2 = 1225 36 2 = 1296 37 2 = 1369 38 2 = 1444 39 2 = 1521 40 2 = 1600 41 2 = 1681 42 2 = 1764 43 2 = 1849 44 2 = 1936
source to share
here is what i tried:
>>> def isperferct_square(n):
... return int(math.sqrt(n))*int(math.sqrt(n)) == n
...
>>> isperferct_square(10)
False
>>> isperferct_square(9)
True
>>> isperferct_square(10000000000000000000)
False
>>> isperferct_square(112312424354957359732985732897583297592735932)
False
>>> isperferct_square(10000000000)
True
>>>
source to share
There are several errors in the code, for example numbers = map (int, raw_input (). Split ()) should be outside the loop. It's the same with counter = 0. Anyway, here's the code for you that should work even for very large numbers:
t = map(int,raw_input().split())
def is_perfect_square(x):
if x < 0:
raise ValueError('square root not defined for negative numbers')
n = int(x)
if n == 0:
return False
a, b = divmod(n.bit_length(), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
count = 0
for i in t:
if is_perfect_square(i)**2 == i:
count+=1
print count
source to share