Как проверить является ли число полным квадратом python
Перейти к содержимому

Как проверить является ли число полным квадратом python

  • автор:

Определить, является ли заданное число квадратом простого числа

Дано натуральное число N. Определить, является ли оно квадратом простого числа.
Формат выходных данных: Вывести в выходной файл Yes, если N — квадрат простого и No в обратном случае.

При загрузке кода в контестер выдаёт, что код справился в 16 из 20 случаев, то есть я что-то не учёл, не могу понять что.

1 2 3 4 5 6 7 8
import math with open('./input.txt', mode='r', encoding='utf_8') as num: x = math.sqrt(float(num.readline())) with open('./output.txt', mode='w', encoding='utf_8') as out: if x % 1 == 0: out.write('Yes') else: out.write('No')

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Дано натуральное число N. Определить, является ли оно квадратом простого числа
Во входном файле записано N (N≤100000). Вывести в выходной файл Yes, если N — квадрат простого и.

Определить является ли число квадратом простого числа
Всем привет, нужна помощь. Есть задача: Дано натуральное число N. Определить, является ли оно.

Проверить, является ли заданное число N квадратом целого числа
Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 0.2 секунды.

Проверить является ли заданное число квадратом целого числа
Проверьте,является ли заданное число N квадратом целого числа.Если заданное число является.

Определить, можно ли заданное число представить в виде куба простого числа
Дано натуральное число N. Определить, можно ли его представить в виде куба простого числа. Я.

Проверить, является ли число полным квадратом

Учитывая положительное число, проверьте, является ли оно идеальным квадратом, не используя встроенную библиотечную функцию. Полный квадрат — это число, являющееся квадратом целого числа.

Input: n = 25
Output: true
Explanation: 25 is a perfect square since it can be written as 5×5.

Input: n = 20
Output: false
Explanation: 20 is not the product of an integer with itself.

1. Использование свойства Perfect Square

Каждый совершенный квадрат удовлетворяет тому свойству, что он представляет собой сумму нечетных чисел, начинающихся с единицы. Например,

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9

n = 1 + 3 + 5 + … + (2*n-1)

Мы можем использовать это свойство, чтобы определить, является ли число n совершенный квадрат или нет. Идея состоит в том, чтобы многократно вычитать нечетные числа из n , начиная с 1, пока не станет 0 или отрицательным. Если значение достигает 0 в какой-то момент, мы можем сказать, что число является идеальным квадратом. Однако, если значение становится отрицательным, не достигая 0, число не может быть идеальным квадратом. Это показано ниже на C++, Java и Python.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

eegmak

Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.

Более простой в реализации, но менее быстрый метод вычисления корня — бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2

Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.

Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра — это такая проверка для модуля по любому простому числу (а не 10).

Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) — равен 1 или 0 (По научному: n — должно быть квадратичным вычетом).

Тут проблема в том, что это необходимый, но недостаточный критерий — если для какого-то p вы получили -1 — то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).

Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 — то точно не квадрат. Иначе — скорее всего квадрат.

Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.

Анализ алгоритма

Пусть a = . Если a * a = n , то число n является полным квадратом.

Пусть n = 27. Тогда a = = 5 . Проверяем: 5 * 5 ≠ 27, следовательно 27 не является полным квадратом.

Читаем действительное число n .

Вычисляем a = .

Если a * a = n , то число n является полным квадратом.

if (a * a == n) printf( «%d\n» , a);

import java.util.*;

class Main

public static void main(String[] args )

Scanner con = new Scanner(System. in );

double n = con .nextDouble();

int a = ( int )Math.sqrt( n );

if ( a * a == n )

System. out .println( a );

System. out .println( «No» );

import math

n = float ( input ())

a = int (math.sqrt(n))

if a * a == n: print (a)

else : print ( «No» )

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *