Python - Fastest way to find all perfect squares in a given large number range

python-3.x square-root perfect-square
Vrashabh Irde picture Vrashabh Irde · Apr 13, 2013 · Viewed 8.3k times · Source

I am trying to write a method to get all the perfect squares in a given range in Python. A large range like between 2621163 and 520001400002. Now obviously iterating through the range and checking if a number is perfect like so 

def is_square(n):
    return math.sqrt(n).is_integer()

and then printing it is stupid for large ranges (works great for small ranges) and will take forever. I am wondering if there is any Python magic or mathemagic (say a modified Diophantine equation) that I can leverage for this purpose.

EDIT: Also I am using Python 3.X so I can use large integers.

Answer

grc picture grc · Apr 13, 2013

You can simply find the smallest and largest numbers that have squares in the specified range. Then you can return the squares of every number in that range.

import math

def perfect_squares(min, max):
    lowest = int(math.ceil(math.sqrt(min)))
    highest = int(math.sqrt(max))
    return (n**2 for n in range(lowest, highest + 1))

Related questions

Convert bytes to a string

I'm using this code to get standard output from an external program: >>> from subprocess import * >>> command_stdout = Popen(['ls', '-l'], stdout=PIPE).communicate()[0] The communicate() method returns an array of bytes: >>> …

Read More
Best way to convert string to bytes in Python 3?

There appear to be two different ways to convert a string to bytes, as seen in the answers to TypeError: 'str' does not support the buffer interface Which of these methods would be better or more Pythonic? Or is it …

Read More
How to install pip with Python 3?

I want to install pip. It should support Python 3, but it requires setuptools, which is available only for Python 2. How can I install pip with Python 3?

Read More