Check if a number is a perfect square
Как я могу проверить, является ли число идеальным квадратом?
Скорость не имеет значения, пока просто работает.
30 ответов
Проблема с использованием любых вычислений с плавающей запятой (math.sqrt(x), или же x**0.5 в том, что вы не можете быть уверены, что это точно (для достаточно больших целых x, это не будет, и может даже переполниться). К счастью (если никто не спешит;-), есть много чистых целочисленных подходов, таких как следующие...:
def is_square(apositiveint):
x = apositiveint // 2
seen = set([x])
while x * x != apositiveint:
x = (x + (apositiveint // x)) // 2
if x in seen: return False
seen.add(x)
return True
for i in range(110, 130):
print i, is_square(i)
Подсказка: он основан на "вавилонском алгоритме" для квадратного корня, см. Википедию. Он работает для любого положительного числа, для которого у вас достаточно памяти для завершения вычислений;-).
Изменить: давайте посмотрим на пример...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
это печатает по желанию (и в разумные сроки, тоже;-):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Пожалуйста, прежде чем предлагать решения, основанные на промежуточных результатах с плавающей запятой, убедитесь, что они правильно работают на этом простом примере - это не так сложно (вам просто нужно несколько дополнительных проверок на случай, если вычисленный sqrt немного отключен), просто требуется немного заботы.
А потом попробуй с x**7 и найти умный способ обойти проблему, которую вы получите,
OverflowError: long int too large to convert to float
вам, конечно, придется становиться все умнее и умнее, так как цифры продолжают расти.
Если бы я спешил, конечно, я бы использовал gmpy - но тогда я явно предвзято;-).
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
Да, я знаю, это так просто, что это похоже на мошенничество (немного то, что я чувствую к Python в целом;-) - никакой хитрости вообще, просто совершенная прямолинейность и простота (и, в случае gmpy, абсолютная скорость;-)...
Используйте метод Ньютона, чтобы быстро найти ближайший целочисленный квадратный корень, затем возведите в квадрат и посмотрите, является ли это вашим числом. Смотри isqrt.
Если вам интересно, у меня есть чисто математический ответ на аналогичный вопрос на математическом стеке: "Обнаружение идеальных квадратов быстрее, чем путем извлечения квадратного корня".
Моя собственная реализация isSquare(n) может быть не самой лучшей, но мне она нравится. Мне потребовалось несколько месяцев изучения математической теории, цифровых вычислений и программирования на Python, сравнивая себя с другими участниками и т. Д., Чтобы по-настоящему использовать этот метод. Мне нравится его простота и эффективность, хотя. Я не видел лучше. Скажи мне, что ты думаешь.
def isSquare(n):
## Trivial checks
if type(n) != int: ## integer
return False
if n < 0: ## positivity
return False
if n == 0: ## 0 pass
return True
## Reduction by powers of 4 with bit-logic
while n&3 == 0:
n=n>>2
## Simple bit-logic test. All perfect squares, in binary,
## end in 001, when powers of 4 are factored out.
if n&7 != 1:
return False
if n==1:
return True ## is power of 4, or even power of 2
## Simple modulo equivalency test
c = n%10
if c in {3, 7}:
return False ## Not 1,4,5,6,9 in mod 10
if n % 7 in {3, 5, 6}:
return False ## Not 1,2,4 mod 7
if n % 9 in {2,3,5,6,8}:
return False
if n % 13 in {2,5,6,7,8,11}:
return False
## Other patterns
if c == 5: ## if it ends in a 5
if (n//10)%10 != 2:
return False ## then it must end in 25
if (n//100)%10 not in {0,2,6}:
return False ## and in 025, 225, or 625
if (n//100)%10 == 6:
if (n//1000)%10 not in {0,5}:
return False ## that is, 0625 or 5625
else:
if (n//10)%4 != 0:
return False ## (4k)*10 + (1,9)
## Babylonian Algorithm. Finding the integer square root.
## Root extraction.
s = (len(str(n))-1) // 2
x = (10**s) * 4
A = {x, n}
while x * x != n:
x = (x + (n // x)) >> 1
if x in A:
return False
A.add(x)
return True
Довольно прямо вперед. Сначала он проверяет, что у нас есть целое и положительное число. Иначе нет смысла. Он пропускает 0 как True (необходимо, иначе следующий блок - бесконечный цикл).
Следующий блок кода систематически удаляет степени 4 в очень быстром под-алгоритме, использующем битовые сдвиги и битовые логические операции. В конечном итоге мы не находим isSquare нашего исходного n, а k Третий блок кода выполняет простой булево-логический тест. Наименее значимые три цифры в двоичном коде любого идеального квадрата - 001. Всегда. В любом случае, за исключением начальных нулей, получаемых из степеней 4, которые уже были учтены. Если тест не пройден, вы сразу узнаете, что это не квадрат. Если это пройдет, вы не можете быть уверены. Кроме того, если мы получим 1 для тестового значения, то тестовый номер изначально был степенью 4, включая, возможно, саму 1. Как и в третьем блоке, четвертый проверяет однозначное значение в десятичном виде с помощью простого оператора модуля и стремится отловить значения, которые проскальзывают в предыдущем тесте. Также мод 7, мод 8, мод 9 и мод 13 тест. Пятый блок кода проверяет некоторые из известных шаблонов совершенных квадратов. Числам, оканчивающимся на 1 или 9, предшествует число, кратное четырем. И числа, заканчивающиеся на 5, должны заканчиваться на 5625, 0625, 225 или 025. Я включил другие, но понял, что они были избыточны или никогда не использовались. Наконец, шестой блок кода очень напоминает ответ главного мэра Алекса Мартелли. В основном находит квадратный корень, используя древний вавилонский алгоритм, но ограничивая его целочисленными значениями, игнорируя с плавающей запятой. Сделано как для скорости, так и для увеличения величин проверяемых величин. Я использовал наборы вместо списков, потому что это занимает гораздо меньше времени, я использовал сдвиги битов вместо деления на два, и я разумно выбрал начальное начальное значение гораздо более эффективно. Кстати, я проверил рекомендованный номер теста Алекса Мартелли, а также несколько чисел на много порядков больше, например: напечатаны следующие результаты: И сделал это за 0,33 секунды. По моему мнению, мой алгоритм работает так же, как алгоритм Алекса Мартелли, со всеми его преимуществами, но имеет дополнительное преимущество - высокоэффективные отклонения простых тестов, которые экономят много времени, не говоря уже об уменьшении размера тестовых чисел степенями 4, что повышает скорость, эффективность, точность и размер чисел, которые могут быть проверены. Вероятно, особенно актуально в не-Python реализации. Примерно 99% всех целых чисел отбрасываются как неквадратные, прежде чем даже вавилонское извлечение корней будет реализовано, и в 2/3 времени потребуется вавилонское отклонение целого числа. И хотя эти тесты не значительно ускоряют процесс, сокращение всех тестовых чисел до нечетного путем деления всех степеней на 4 действительно ускоряет вавилонский тест. Я сделал тест сравнения времени. Я проверил все целые числа от 1 до 10 миллионов подряд. Используя сам по себе вавилонский метод (с моим специально подобранным начальным предположением), для моего Surface 3 потребовалось в среднем 165 секунд (со 100% точностью). Используя только логические тесты в моем алгоритме (исключая вавилонский), это заняло 127 секунд, он отклонил 99% всех целых чисел как неквадратные, по ошибке не отклонив ни одного идеального квадрата. Из тех целых чисел, которые прошли, только 3% были идеальными квадратами (гораздо более высокой плотности). Используя приведенный выше полный алгоритм, который использует как логические тесты, так и извлечение вавилонских корней, мы получаем 100% точность и завершение теста всего за 14 секунд. На первые 100 миллионов целых чисел уходит примерно 2 минуты 45 секунд. РЕДАКТИРОВАТЬ: я был в состоянии сократить время дальше. Теперь я могу проверить целые числа от 0 до 100 миллионов за 1 минуту 40 секунд. Потрачено много времени на проверку типа данных и положительности. Исключите первые две проверки, и я сократил эксперимент на минуту. Надо полагать, что пользователь достаточно умен, чтобы знать, что негативы и поплавки не являются идеальными квадратами.x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
Поскольку вы никогда не можете зависеть от точных сравнений при работе с вычислениями с плавающей запятой (такими как эти способы вычисления квадратного корня), менее подверженная ошибкам реализация будет
import math
def is_square(integer):
root = math.sqrt(integer)
if int(root + 0.5) ** 2 == integer:
return True
else:
return False
Представить integer является 9, math.sqrt(9) может быть 3.0, но это также может быть что-то вроде 2.99999 или же 3.00001так что квадрат результата сразу не надежен. Знаю это int принимает значение пола, увеличивая значение с плавающей точкой на 0.5 первое означает, что мы получим значение, которое мы ищем, если мы находимся в диапазоне, где float все еще имеет достаточно хорошее разрешение для представления чисел рядом с тем, который мы ищем.
import math
if (math.sqrt(number)-int(math.sqrt(number))):
print "it's not a perfect square"
Идеальный квадрат - это число, которое можно выразить как произведение двух равных целых чисел. math.sqrt(number) вернуть float, int(math.sqrt(number)) бросает результат на int,
Если квадратный корень является целым числом, например, 3, то math.sqrt(number) - int(math.sqrt(number)) будет 0, а if заявление будет False, Если квадратный корень был действительным числом, таким как 3,2, то он будет True и выведите "это не идеальный квадрат".
Мой ответ будет:
def checkSquare(x):return x**.5%1==0
Это в основном делает квадратный корень, затем по модулю 1, чтобы убрать целую часть, и если результат равен 0, вернуть True в противном случае возврат False, В этом случае x может быть любым большим числом, но не таким большим, как максимальное число с плавающей запятой, которое может обработать python: 1.7976931348623157e+308
Это можно решить с помощью decimal Модуль для получения произвольной точности квадратного корня и простой проверки на "точность":
import math
from decimal import localcontext, Context, Inexact
def is_perfect_square(x):
# If you want to allow negative squares, then set x = abs(x) instead
if x < 0:
return False
# Create localized, default context so flags and traps unset
with localcontext(Context()) as ctx:
# Set a precision sufficient to represent x exactly; `x or 1` avoids
# math domain error for log10 when x is 0
ctx.prec = math.ceil(math.log10(x or 1)) + 1 # Wrap ceil call in int() on Py2
# Compute integer square root; don't even store result, just setting flags
ctx.sqrt(x).to_integral_exact()
# If previous line couldn't represent square root as exact int, sets Inexact flag
return not ctx.flags[Inexact]
Для демонстрации с действительно огромными ценностями:
# I just kept mashing the numpad for awhile :-)
>>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324
>>> sqr = base ** 2
>>> sqr ** 0.5 # Too large to use floating point math
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float
>>> is_perfect_power(sqr)
True
>>> is_perfect_power(sqr-1)
False
>>> is_perfect_power(sqr+1)
False
Если вы увеличиваете размер тестируемого значения, это в конечном итоге становится довольно медленным (занимает около секунды для 200 000-битных квадратов), но для более умеренных чисел (скажем, 20 000-битных) это все же быстрее, чем человек заметил бы для индивидуальные значения (~33 мс на моей машине). Но так как скорость не была вашей главной задачей, это хороший способ сделать это со стандартными библиотеками Python.
Конечно, было бы гораздо быстрее использоватьgmpy2 и просто проверить gmpy2.mpz(x).is_square(), но если сторонние пакеты - не ваша вещь, вышеприведенное работает довольно хорошо.
Я новичок в Stack Overflow и быстро просмотрел решение. Я только что опубликовал небольшую вариацию некоторых примеров выше в другом потоке ( Поиск идеальных квадратов) и подумал, что я бы включил небольшую вариацию того, что я здесь написал (используя nsqrt как временную переменную), на случай, если это будет интересно / использовать:
import math
def is_perfect_square(n):
if not ( isinstance(n, (int, long)) and ( n >= 0 ) ):
return False
else:
nsqrt = math.sqrt(n)
return nsqrt == math.trunc(nsqrt)
Вариант решения @Alex Martelli без set
когда x in seen является True:
- В большинстве случаев он добавляется последним, например 1022 дает
xпоследовательность 511, 256, 129, 68, 41, 32, 31, 31; - В некоторых случаях (например, для предшественников полных квадратов) добавляется предпоследний, например 1023 дает 511, 256, 129, 68, 41, 32, 31, 32.
Следовательно, достаточно остановиться, как только текущая x больше или равно предыдущему:
def is_square(n):
assert n > 1
previous = n
x = n // 2
while x * x != n:
x = (x + (n // x)) // 2
if x >= previous:
return False
previous = x
return True
x = 12345678987654321234567 ** 2
assert not is_square(x-1)
assert is_square(x)
assert not is_square(x+1)
Эквивалентность оригинальному алгоритму проверена для 1
Если это идеальный квадрат, его квадратный корень будет целым числом, дробная часть будет равна 0, мы можем использовать оператор модуля, чтобы проверить дробную часть, и проверить, равен ли он 0, он не работает для некоторых чисел, поэтому для безопасности мы также проверит, является ли это квадратом квадратного корня, даже если дробная часть равна 0.
import math
def isSquare(n):
root = math.sqrt(n)
if root % 1 == 0:
if int(root) * int(root) == n:
return True
return False
isSquare(4761)
Остаток или модуль квадратного корня из числа, не имеющего остатка, означает, что это полный квадрат. Модуль - это встроенная функция во всех версиях Python.
def is_square(num: int) -> bool:
return num % math.sqrt(num) == 0
Я проверил это по списку идеальных квадратов, доходящему до 1000.
Можно улучшить вавилонский метод, заметив, что следующие друг за другом члены образуют убывающую последовательность, если один начинает больше квадратного корня из n.
def is_square(n):
assert n > 1
a = n
b = (a + n // a) // 2
while b < a:
a = b
b = (a + n // a) // 2
return a * a == n
Это мой метод
int(n**0.5)**2 == int(n)
взять квадратный корень из числа, преобразовать в целое число, затем взять квадрат, если числа равны, тогда это идеальный квадрат, иначе нет.
Простой способ сделать это (быстрее, чем второй):
def is_square(n):
return str(n**(1/2)).split(".")[1] == '0'
Другой путь:
def is_square(n):
if n == 0:
return True
else:
if n % 2 == 0 :
for i in range(2,n,2):
if i*i == n:
return True
else :
for i in range(1,n,2):
if i*i == n:
return True
return False
Вы можете выполнить двоичный поиск для округленного квадратного корня. Возведите в квадрат результат, чтобы увидеть, соответствует ли оно исходному значению.
Вам, вероятно, лучше с ответом FogleBirds - хотя остерегайтесь, поскольку арифметика с плавающей запятой приблизительна, что может отбросить этот подход. В принципе, вы можете получить ложный положительный результат из большого целого числа, которое на единицу больше идеального квадрата, например, из-за потери точности.
Это элегантное, простое, быстрое и произвольное решение, которое работает для версии Python >= 3.8:
from math import isqrt
def is_square(number):
if number >= 0:
return isqrt(number) ** 2 == number
return False
Если вы хотите перебрать диапазон и сделать что-то для каждого числа, которое НЕ является идеальным квадратом, вы можете сделать что-то вроде этого:
def non_squares(upper):
next_square = 0
diff = 1
for i in range(0, upper):
if i == next_square:
next_square += diff
diff += 2
continue
yield i
Если вы хотите сделать что-то для каждого числа, которое является идеальным квадратом, генератор еще проще:
(n * n for n in range(upper))
Этот ответ относится не к указанному вами вопросу, а к неявному вопросу, который я вижу в опубликованном вами коде, т. Е. "Как проверить, является ли что-то целым?"
Первый ответ, который вы обычно получите на этот вопрос: "Не надо!" И это правда, что в Python проверка типов обычно не правильная вещь.
Однако для этих редких исключений вместо поиска десятичной точки в строковом представлении числа нужно использовать функцию isinstance:
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Конечно, это относится к переменной, а не к значению. Если бы я хотел определить, является ли значение целым числом, я бы сделал это:
>>> x=5.0
>>> round(x) == x
True
Но, как все остальные подробно рассмотрели, есть проблемы с плавающей запятой, которые следует учитывать в большинстве неигровых примеров такого рода вещей.
- Решите, как долго номер будет.
- принять дельта 0.000000000000.......000001
- посмотрите, больше ли (равно / x))^2 - x, больше / равно / меньше дельты, и решите, основываясь на ошибке дельты.
Численно это настолько наивное решение, насколько это возможно. Это работает для небольших номеров.
def is_perfect_square(n):
return (n ** .5).is_integer()
Очевидно, что это не удается для большого числа, таких как 152415789666209426002111556165263283035677490.
Я не уверен в Питоне, но вы могли бы сделать что-то вроде:
function isSquare(x) = x == floor(sqrt(x) + 0.5)^2
То есть возьмите число, найдите квадратный корень, округлите его до ближайшего целого числа, возведите в квадрат и проверьте, совпадает ли оно с исходным числом. (floor и добавление 0.5 сделано для предотвращения таких случаев, как sqrt(4) возврате 1.9999999... из-за математики с плавающей точкой, как указал Майк Грэм.)
Если вам интересно, когда-то было очень хорошее обсуждение о том, как быстрее всего определить, является ли целочисленный квадратный корень целым числом.
Отредактировано для уточнения.
Вероятно, самый простой способ - сказать
def perfectSquare(x):
return (x == math.isqrt(x) ** 2)
Этот алгоритм уже довольно быстр, поскольку для нахождения целочисленного квадратного корня он использует метод Ньютона. Однако можно выделить множество чисел, которые никогда не будут квадратом. Например, когда вы беретеx % 16, только остатки0, 1, 4, 9необходимо проверить на соответствиеisqrt(x)метод. Если метод isqrt недоступен, можно также использовать идею вавилонского метода и объединить ее с идеей по модулю, чтобы получить
def perfectSquare(n):
m = n % 16
if m != 0 and m != 1 and m != 4 and m != 9:
return False
x = n
while x * x > n:
x = (x + n // x) // 2
return x * x == n
Для более глубокого объяснения посмотрите вывод .
Я думаю, что это работает и очень просто:
from math import sqrt
def is_perfect_square(num):
return int(sqrt(num)) == sqrt(num)
a=int(input('enter any number'))
flag=0
for i in range(1,a):
if a==i*i:
print(a,'is perfect square number')
flag=1
break
if flag==1:
pass
else:
print(a,'is not perfect square number')
В Котлине:
Это довольно просто, и он также прошел все тестовые случаи.
действительно благодаря >> https://www.quora.com/What-is-the-quickest-way-to-determine-if-a-number-is-a-perfect-square
fun isPerfectSquare(num: Int): Boolean {
var result = false
var sum=0L
var oddNumber=1L
while(sum<num){
sum = sum + oddNumber
oddNumber = oddNumber+2
}
result = sum == num.toLong()
return result
}
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left <= right:
mid = (left + right) // 2
if mid**2 < num:
left = mid + 1
elif mid**2 > num:
right = mid - 1
else:
return True
return False
Идея состоит в том, чтобы запустить цикл от i = 1 до этажа (sqrt(n)), а затем проверить, дает ли возведение в квадрат n.
bool isPerfectSquare(int n)
{
for (int i = 1; i * i <= n; i++) {
// If (i * i = n)
if ((n % i == 0) && (n / i == i)) {
return true;
}
}
return false;
}
Существует ОЧЕНЬ простой способ сделать это. Найти, сколько факторов число имеет (в том числе один и сам). Если это имеет нечетное количество факторов, это квадрат.
def getFactors(n):
'''Code for counting factors of n.'''
result = 1 # not forgetting to count the number itself
for i in range(1, n // 2 + 1):
if n % i == 0:
result += 1
return resultЕсли результат функции нечетный, это квадрат.
РЕДАКТИРОВАТЬ:
Возможно, это не лучший метод для компьютерной программы, но это хороший метод для людей.
У меня есть небольшое улучшение оригинального решения с использованием вавилонского подхода. Вместо использования набора для хранения каждого ранее сгенерированного приближения сохраняются только последние два приближения, которые сравниваются с текущим приближением. Это экономит огромное количество времени, потраченного на проверку всего набора предыдущих приближений. Я использую Java вместо Python и класс BigInteger вместо обычного примитивного целого числа.
BigInteger S = BigInteger.ZERO;
BigInteger x = BigInteger.ZERO;
BigInteger prev1 = BigInteger.ZERO;
BigInteger prev2 = BigInteger.ZERO;
Boolean isInt = null;
x = S.divide(BigInteger.valueOf(2));
while (true) {
x = x.add(preA.divide(x)).divide(BigInteger.valueOf(2));
if (x.pow(2).equals(S)) {
isInt = true;
break;
}
if (prev1.equals(x) || prev2.equals(x)) {
isInt = false;
break;
}
prev2 = prev1;
prev1 = x;
}