Является ли число квадратом или кубом некоторого натурального числа, как это определить.
Числа, заканчивающиеся на 2, 3, 7, 8 — не могут быть точными квадратами
Числа, заканчивающиеся на Х0 (если Х не 0) — не могут быть точными квадратами
Числа, заканчивающиеся на Х5 (если Х не 2) — не могут быть точными квадратами
Числа, заканчивающиеся на Х6 (если Х четное ) — не могут быть точными квадратами
и т. д. можно много ограничителей найти, чтоб зря не извлекать. Также и для кубов, потренируйтесь.
Как узнать является ли число квадратом
Дано натуральное число. Определить, является ли оно квадратом какого либо натурального числа.
Для того чтобы определить является ли заданное натуральное число квадратом какого либо другого натурального числа мы поступим следующим образом. Извлечем корень квадратный из нашего натурального числа (получится действительное число). Округлим его до целого числа. Если квадрат этого нового целого числа будет равен исходному числу, значит заданное натуральное число и является квадратом другого натурального числа.
Например: округление равно 7 и 7 2 = 49.
округление равно 7, но 7 2 ≠ 50
округление равно 7, но 7 2 ≠ 48.
Примечания для Pascal : В Pascal корень квадратный ( ) — функция sqrt ,
а округление – функция round .
Примечания для С++ : В С++ корень квадратный ( ) — функция sqrt , а округление до целого мы произведем так — a =( int ) sqrt ( n +0.5); то есть получим чуть большее число и удалим у него дробную часть. ( int ) поставленное перед любым выражением отбрасывает дробную часть. Хотя можно признаться, что и в С++ можно округление выполнить так a =( int ) round ( sqrt ( n ));
Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?
Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.
Более простой в реализации, но менее быстрый метод вычисления корня — бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2 <= n <= r^2. Изначально можно сделать l=1, r=10^51 (или больше — половина длины входного числа + немного, чтобы точно квадрат был больше n), потом делить отрезок пополам и отбрасывать ненужную половину.
Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.
Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра — это такая проверка для модуля по любому простому числу (а не 10).
Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) — равен 1 или 0 (По научному: n — должно быть квадратичным вычетом).
Если брать небольшие (<64-битные) простые числа, то можно за линию считать n%p и потом вычислять символ Лежандра (n%p/p) по алгоритму через символ Якоби за O(log(p)^2). Когда подсчитали символ Лежандра и если он -1, то n — точно не корень.
Тут проблема в том, что это необходимый, но недостаточный критерий — если для какого-то p вы получили -1 — то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).
Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 — то точно не квадрат. Иначе — скорее всего квадрат.
Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.
Признак квадрата натурального числа?
Признак делимости числа на 7
Дано число в виде 10А + В. Если мы умножим это число на 5, то получим другое число. Причем оба.
Первые два числа квадрата
Есть число, где первая цифра например Х. Затем возводим это число в квадрат и получаем, что первые.
Поиск позиции квадрата числа в последовательности
Пытаюсь оптимизировать алгоритм для поиска простых чисел и возник вопрос в создании формулы.
Расставьте в клетках квадрата 10х10 различные натуральные числа
Здравствуйте. Есть задача. Расставьте в клетках квадрата 10х10 различные натуральные числа так.
Сообщение было отмечено ili1 как решение
Решение
Можно заметить, что N — 1 = k 2 — 1 = (k-1)(k+1) — то есть является произведением 2-х "почти соседних" чисел. Сам k близок к корню из N. Напрашивается такой конечный алгоритм. Полагаем k = (int)sqrt(N). Если (k-1)(k+1) < N, увеличиваем k, пока это произведение не станет = N-1 (тогда — Yes!) или больше (No!) Ну и наоборот.