Как эффективно находить идеальные квадраты в диапазоне, когда в Python вводятся большие числа

Вопрос в том, как эффективно найти идеальные квадраты в заданном диапазоне, когда входные данные очень большие. Мое решение дает Time Limit Exceeded ошибка. Я уже проверил следующие ссылки, но они не решили мою проблему:
- программа Python на идеальных квадратах
- Как я могу проверить, является ли число идеальным квадратом?
- Самый быстрый способ определить, является ли целочисленный квадратный корень целым числом (я понятия не имею, как реализовать решение, приведенное в этой ссылке в Python).

Проблемный вопрос:

Формат ввода: Первая строка содержит T, количество тестовых случаев. Далее следуют тесты T, каждый в новой строке. Каждый тестовый пример содержит два целых числа, разделенных пробелами, обозначающих A и B. Найдите все идеальные квадраты в диапазоне A и B (оба включительно).

Пример ввода:

2
3 9
17 24

Код, который я написал:

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

Хотя этот код работает для меньших чисел, он дает Time limit exceeded ошибка для больших входов.

(НОТА: gmpy это не вариант, так как код должен выполняться на онлайн-компиляторе, который не имеет gmpy модуль)

Источник

3 ответа

Решение

Вместо зацикливания от A в B и проверка на идеальные квадраты, почему бы просто не перебрать целые числа из sqrt(A) в sqrt(B) и квадрат каждого, давая вам ваш ответ.

Например, давайте найдем квадратные числа между 1000 и 2000:

sqrt(1000) = 31.6  -->  32  (need the ceiling here)
sqrt(2000) = 44.7  -->  44  (need the floor here)

Поэтому наш ответ:

322 = 1024
332 = 1089
342 = 1156
352 = 1225
362 = 1296
372 = 1369
382 = 1444
392 = 1521
402 = 1600
412 = 1681
422 = 1764
432 = 1849
442 = 1936
Источник

В вашем коде есть несколько ошибок, например, число = карта (int, raw_input(). Split()) должно быть за пределами цикла. То же самое со счетчиком =0. В любом случае, вот код для вас, который должен работать даже для действительно больших целых чисел:

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
Источник

Вот что я пробовал:

>>> 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
>>>
Источник
Другие вопросы по тегам