CODEWITHSUNDEEP
python-3.xsquare-rootperfect-square
Vrashabh Irde
Vrashabh Irde

Reputation: 14367

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

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.

Upvotes: 3

Views: 10621

Answers (6)

Zulqarnain Khan
Zulqarnain Khan

Reputation: 3

You realize that if you know the first and last closest perfect square, the rest is just the range between them. I would calculate it this way:

import math

def all_squares(a,b):#a is the starting point whereas b is the end of range
    smallest = int(math.ceil(math.sqrt(a)))#perfect square closest to lower bound (rounded up)
    largest = int(math.sqrt(b))#perfect square closest to upper bound (rounded down)
    squares = []
    for s in range(smallest, largest+1):
        squares.append(s**2)
    return squares

Upvotes: 0

Rohit
Rohit

Reputation: 1

Simple python code with out using functions

import math
num=500
for i in range(1,math.ceil(math.sqrt(num))):
    print(i*i)

Upvotes: 0

Sonu Sharma
Sonu Sharma

Reputation: 11

getting perfect square from 1 to 100 digit using numpy

import numpy as np

a={int(np.sqrt(x)) for x in range(1,101)}

b= np.power(list(a),2) 

print(a)

print(b)

Upvotes: 0

grc
grc

Reputation: 23575

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))

Upvotes: 11

Hussain
Hussain

Reputation: 9

Imagine the number is 34929456, you can come to know it isn't a perfect square as when it's split up 3:4:9:2:9:4:5:6= 42. 42 isn't a square number so that means 34929456 isn't a perfect square! (I'm not using a calculator for any of this) Now we know it isn't a perfect square, you'll round it up/Down... So, you take the last 2 digits, 56! To make 56 with single digits is 7(Times)8=56! 34929456 is a 8 digit number so that means 8-7=1+4=5. So that means the answer is between 5000 and 6000. Now, you do a little guessing. Let's do 5500 squared= 30250000. So we know the square root is a bit bigger! Now let's try 5910. 5910 squared = 34928100. So know we know the answer is between 5910 and 5911! Thanks for reading! :P, Hope it helped!

Upvotes: 0

Itay Karo
Itay Karo

Reputation: 18296

def perfect_squares(start, stop):
  return (i*i for i in xrange(math.ceil(math.sqrt(start)), math.floor(math.sqrt(stop)) + 1))

Upvotes: 0

Related Questions