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

Как выяснить степенью какого числа является число

  • автор:

Как проверить, является ли заданное число степенью двойки?

Как проверить, является ли заданное число степенью двойки. Например: 256 = 2^8 8 = 2^3 Как можно это осуществить в C#?

Отслеживать
13.8k 12 12 золотых знаков 44 44 серебряных знака 77 77 бронзовых знаков
задан 21 фев 2021 в 12:19
37 1 1 золотой знак 2 2 серебряных знака 5 5 бронзовых знаков

Степень двойки делается простым регистровым сдвигом 2
21 фев 2021 в 12:33
Ага, либо воспользоваться школьными знаниями о логарифмах: взять логарифм по основанию два.
21 фев 2021 в 12:38
21 фев 2021 в 12:49
Для целых, как и в любом С-подобном языке — if ((x & (x — 1)) == 0) < // это степень двойки >
21 фев 2021 в 13:21
Хороший простой вопрос. Не вижу смысла минусовать или ставить флаг за закрытие ¯_(ヅ)_/¯
21 фев 2021 в 13:22

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

n > 0 && (n & (n - 1)) == 0 

Там по ссылке ещё много всяких битовых трюков.

Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n . У числа n — 1 будет на месте этой единицы ноль, а справа от него единицы:

n : xxxxxx1000 1 : 0000000001 n - 1 : xxxxxx0111 

а остальные двоичные цифры (обозначенные как x ) не поменяются. Поэтому после операции & получится вот что:

n&(n-1): xxxxxx0000 

Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.

Как узнать степень числа?

К примеру есть число 614656 равное 28^4(28 в степени 4-ре) . Если знаешь только 614656 как можно вычислить математически что это 28^4? Если можно напишите формулу.

Лучший ответ

Самое разумное разложить число на простые множители, тогда можно найти и основание и показатель степени.
Если известно основание, то показатель можно найти логарифмированием, например,
2^x=8
Чтобы найти x нужно прологарифмировать обе части по основанию 2
x = log по основанию 2 от 8 = ln 8 / ln 2 (так можно на калькуляторе посчитать) = 3
Если известен показатель, то основание находится извлечением корня, например,
x^3=8
извлекаем корень кубический из обоих частей
x=корень кубический из 8 = 2

Если же неизвестно ни то ни другое разложи число на простые множители, это делается последовательным делением числа на простые множители
614656 / 2 = 307328
307328 / 2 = 153664
153664 / 2 = 76832
76832 / 2 = 38416
38416 / 2 = 19208
19208 / 2 = 9604
9604 / 2 = 4802
4802 / 2 = 2401
2401 не делится на 2, на 3, на 5 (последовательно перебираем простые числа)
2407 / 7 = 343
343 / 7 = 49
49 / 7 = 7
7 / 7 = 1
Итого мы делили на 2 восемь раз и на 7 четыре раза, следовательно
614656 = 2^8 * 7^4
Если мы хотим найти представление в виде a^b с натуральными a и b и b должно быть максимальным, то в качестве b нужно брать НОД степеней полученных в разложении на простые множители, то есть в данном случае b=НОД (8,4)=4
основанием степени a будет служить 2^(8/b) * 7^(4/b) = 2^2 * 7^1 = 4*7=28

Остальные ответы
На калькулятое возьми в квадратный корень и разложи его

Тут дело в том, что смотря степень какого число тебе надо, если именно 28, то не все числа получится получить, а если 2-ки (что скорее всего единственный верный способ) , то да, возьми калькулятор и посчитай. ) )
Если тебе математически надо)))

Если знаешь основание (в нашем случае 28), то 4 — логарифм 614656 по основанию 28.
Калькулятор умеет считать логарифмы по основанию 2, 10 и e (2.7. ). Но есть формулы для перевода. Подробнее см. http://www.clascalc.ru/logarithm.htm «Логарифм, степень и показательная функция».

да это прогу напписать легко по разложению на простые числа, а самому искать не так-то просто!

Для решения такого рода задач, хорошо иметь
маткад. Там есть функция factor.
А уже по разложению можно найти разные
варианты.

Самый «деревянный», но действенный метод — разложение на множители

разложи на простые множители, т. е. дели на простые числа
1)четные числа делятся на 2, дели пока делятся потом смотри дальше на что делятся, например на 7, в итоге посчитай сколько 2, сколько 7, у тебя 2 в степени.. . *7в степени.

Аналитического способа не существует. То бишь формулы для нахождения степени и числа, которое возводят в эту степень — нет.

Так для общего развития скажу, что даже нахождение достаточно больших простых чисел — занятие затруднительное и очень хорошо оплачиваемое. А для решения вашей задачи (как минимум) нужно знать что это число уже не простое. :)))

Здравствуйте, уважаемый Максим Сальников !

Общей методики для задач такого типа, как мне известно, нет .

Самый простой способ — разложить данное число на простые множители .

В приведённом Вами примере это будет выглядеть так :

614656 = ( 2 x 2 x2 x 2 x 2 x 2 x 2 x 2 ) x ( 7 x 7 x 7 x 7 )

Из 7 x 7 x 7 x 7 следует, что » вероятная степень » равна 4 : 7 x 7 x 7 x 7 = 7 ^ 4 ( 1 )

Тогда из 2 x 2 x2 x 2 x 2 x 2 x 2 x 2 образуем ( 2 x 2 ) x ( 2 x 2 ) x( 2 x 2 ) x ( 2 x 2 ) = 4 ^ 4 ( 2 )

Согласно ( 1 ) и ( 2 ) можем записать : 614656 = ( 4 ^ 4 ) x ( 7 ^ 4 ) = ( 4 x 7 ) ^ 4 = 28 ^ 4 !

Успеха в освоении математики !

С массой наилучших пожеланий и счастья в личной жизни !

Как выяснить степенью какого числа является число

Как определить, является ли число степенью другого?
т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )

Re: определить является ли число степенью

От: MBo
Дата: 15.11.06 11:27
Оценка: +1 -1

Здравствуйте, Amouse, Вы писали:

A>Как определить, является ли число степенью другого?
A>т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )

ну наверно, все же 125 является степенью пятерки.

1 способ. Если большое на малое делится нацело несколько раз, пока не получится единица
2 способ Перевести большое число в систему счисления с основанием малое число, и проверить, что получилось «1000. «

Re[2]: определить является ли число степенью

От: Nirel
Дата: 15.11.06 11:49
Оценка:

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, Amouse, Вы писали:

A>>Как определить, является ли число степенью другого?
A>>т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )

MBo>ну наверно, все же 125 является степенью пятерки.

MBo>1 способ. Если большое на малое делится нацело несколько раз, пока не получится единица
MBo>2 способ Перевести большое число в систему счисления с основанием малое число, и проверить, что получилось «1000. «

Алгоритм номер 2. Как его можно применить, скажем к задаче: 17^17 ?
Или если формулировать вопрос как автор ветки, является ли число 8272[многоцифер]177 степенью числа 17 ?

Re: определить является ли число степенью

От: Кодт
Дата: 15.11.06 12:00
Оценка: 1 (1)

Здравствуйте, Amouse, Вы писали:

A>Как определить, является ли число степенью другого?
A>т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )

Любое число является степенью любого другого (за исключением особых случаев: 0, 1, отрицательные)
Нужно установить: является ли данное число целой степенью. Для этого есть логарифмы.

x = p^n
n = log(x)/log(p)
Осталось только проверить, целое ли число n.

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

С другой стороны, можно чисто в целых числах сделать. Ведь даже log(MAXINT)/log(2) (худший случай, так сказать) равен 32 или 64. Поэтому тупой линейный перебор степеней — p^1, p^2, . не продлится слишком долго.

Перекуём баги на фичи!
Re: определить является ли число степенью

От: Nikolaus
Дата: 15.11.06 12:40
Оценка:

Здравствуйте, Amouse, Вы писали:

A>Как определить, является ли число степенью другого?
A>т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )
Так тривиально
Делить 125 на 5, пока можем или пока не получим 1.

Указал бы размерность задачи и ограничения.

Re[2]: определить является ли число степенью

От: Кодт
Дата: 15.11.06 13:24
Оценка: 1 (1)

Здравствуйте, MBo, Вы писали:

MBo>1 способ. Если большое на малое делится нацело несколько раз, пока не получится единица
MBo>2 способ Перевести большое число в систему счисления с основанием малое число, и проверить, что получилось «1000. «

Способ номер два всё равно реализуется через способ номер один, только с избыточностью.

Перекуём баги на фичи!
Re: определить является ли число степенью

От: Nuzhny https://github.com/Nuzhny007
Дата: 15.11.06 13:29
Оценка: +1

Что-то все: «делить, делить. «. Целые делить так нельзя. А с нецелыми — погрешность.
Умножать меньшее число a само на себя. Если a > b — не является степенью, если a = b — является.

Re[2]: определить является ли число степенью

От: Amouse
Дата: 15.11.06 13:32
Оценка:

Здравствуйте, Nikolaus, Вы писали:

N>Так тривиально
N>Делить 125 на 5, пока можем или пока не получим 1.

ну это обратное от простого перебора которое Кодт указал,
я думал может есть что похитрее .
А размерность — int.

В принципе с log()/log() наверное универсальней всего, только там действительно погрешность надо будет убирать.

Re[3]: определить является ли число степенью

От: FDSC consp11.github.io блог
Дата: 15.11.06 13:32
Оценка: +1

Здравствуйте, Nirel, Вы писали:

N>Алгоритм номер 2. Как его можно применить, скажем к задаче: 17^17 ?
N>Или если формулировать вопрос как автор ветки, является ли число 8272[многоцифер]177 степенью числа 17 ?

А в чём проблема. Переведёшь 8272[многоцифер]177 в 17-ричную систему исчисления и получится у тебя 100000000000000000 — всё полный нормал.

Re[2]: определить является ли число степенью

От: FDSC consp11.github.io блог
Дата: 15.11.06 13:35
Оценка:

Здравствуйте, Nuzhny, Вы писали:

N>Что-то все: «делить, делить. «. Целые делить так нельзя. А с нецелыми — погрешность.

Почему нельзя. Можно. В eax — результат, в edx — остаток. Если остаток ненулевой -прекращаем. Если eax = 1 и edx = 0 — то проверяемое число есть степень.

N>Умножать меньшее число a само на себя. Если a > b — не является степенью, если a = b — является.

Этот способ быстрее.

Re[3]: определить является ли число степенью

От: Nuzhny https://github.com/Nuzhny007
Дата: 15.11.06 14:17
Оценка:

Хотя нет. Умножения чреваты переполнением. И в любом случае понадобится их выполнять минимум b/a раз.

Re[4]: определить является ли число степенью

От: Nuzhny https://github.com/Nuzhny007
Дата: 15.11.06 14:19
Оценка:

Здравствуйте, Nuzhny, Вы писали:

N>Хотя нет. Умножения чреваты переполнением. И в любом случае понадобится их выполнять минимум b/a раз.
Последнее предложение — полная чушь. Прошу прощения — написал не подумав.

Re[5]: определить является ли число степенью

От: Amouse
Дата: 15.11.06 14:46
Оценка:

Здравствуйте, Nuzhny, Вы писали:

N>>Хотя нет. Умножения чреваты переполнением. И в любом случае понадобится их выполнять минимум b/a раз.
N>Последнее предложение — полная чушь. Прошу прощения — написал не подумав.

переполнение не чушь, геморойно довольно отслеживать.

Re[6]: определить является ли число степенью

От: FDSC consp11.github.io блог
Дата: 15.11.06 15:23
Оценка:

Здравствуйте, Amouse, Вы писали:

A>Здравствуйте, Nuzhny, Вы писали:

N>>>Хотя нет. Умножения чреваты переполнением. И в любом случае понадобится их выполнять минимум b/a раз.
N>>Последнее предложение — полная чушь. Прошу прощения — написал не подумав.

A>переполнение не чушь, геморойно довольно отслеживать.

Почему? На asm нормально. а на нормальном языке. извращение, да, согласен.

Re[7]: определить является ли число степенью

От: Кодт
Дата: 15.11.06 15:55
Оценка:

Здравствуйте, FDSC, Вы писали:

A>>переполнение не чушь, геморойно довольно отслеживать.

FDS>Почему? На asm нормально. а на нормальном языке. извращение, да, согласен.

Да ну, бросьте. Никаких извращений.

int p, x; int one_step_to_overflow = MAXINT/p; // для эстетов-сиплюсплюсников: вместо MAXINT - (std::numeric_limits::max) int limit = min(x, one_step_to_overflow); int power = p; while(power < limit) power *= p; // пока power < limit return power == x;

Перекуём баги на фичи!
Re: определить является ли число степенью

От: StatujaLeha на правах ИМХО
Дата: 16.11.06 14:01
Оценка:

Здравствуйте, Amouse, Вы писали:

A>Как определить, является ли число степенью другого?
A>т.е скажем, узнать для числа «5» является ли оно степенью «125». В данном случае это будет верно (т.к — 5, 25, 125. )

Разложить число на простые множители, т.е. n = p1^a1 * p2^a2 * . * pn^an.
Если НОД(a1, a2, . an) = d > 1, то число n = b^d, b = p1^(a1/d) * p2^(a2/d) * . * pn^(an/d).

Re[8]: определить является ли число степенью

От: FDSC consp11.github.io блог
Дата: 16.11.06 17:22
Оценка:

Здравствуйте, Кодт, Вы писали:

К>Да ну, бросьте. Никаких извращений.
К>

К>int p, x; К>int one_step_to_overflow = MAXINT/p; // для эстетов-сиплюсплюсников: вместо MAXINT - (std::numeric_limits::max) К>int limit = min(x, one_step_to_overflow); К>int power = p; К>while(power < limit) power *= p; // пока power < limit К>return power == x; К>

Верно, почему-то я подумал, что вычилять limit нужно в цикле

Re[8]: определить является ли число степенью

От: Nuzhny https://github.com/Nuzhny007
Дата: 17.11.06 06:27
Оценка: 1 (1)

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, FDSC, Вы писали:

A>>>переполнение не чушь, геморойно довольно отслеживать.

FDS>>Почему? На asm нормально. а на нормальном языке. извращение, да, согласен.

К>Да ну, бросьте. Никаких извращений.
К>

К>int p, x; К>int one_step_to_overflow = MAXINT/p; // для эстетов-сиплюсплюсников: вместо MAXINT - (std::numeric_limits::max) К>int limit = min(x, one_step_to_overflow); К>int power = p; К>while(power < limit) power *= p; // пока power < limit К>return power == x; К>

Интересно, а будет ли цикл бесконечным , если power == 1?

Re[9]: определить является ли число степенью

От: Кодт
Дата: 17.11.06 10:21
Оценка:

Здравствуйте, Nuzhny, Вы писали:

N>Интересно, а будет ли цикл бесконечным , если power == 1?

Особые случаи следует обрабатывать до того.
— аргументы равны 0 или ±1 — сразу давать ответ
— положительное p и отрицательное x — сразу отказать
— отрицательное p — найти порядок n : |x|=|p|^n и затем проверить знак x с чётностью n

Перекуём баги на фичи!
Re[2]: определить является ли число степенью

От: Андрей Тарасевич
Дата: 18.11.06 01:47
Оценка:

Здравствуйте, Nuzhny, Вы писали:

N>Что-то все: «делить, делить. «. Целые делить так нельзя. А с нецелыми — погрешность.
N>Умножать меньшее число a само на себя. Если a > b — не является степенью, если a = b — является.

Тут сразу напрашивается алгоритм типа ‘Russian peasant’. Т.е. растить степень ‘a’ не линейно, а квадратично. Вот, например (без проверки переполнений и особых ситуаций)

bool is_power(unsigned a, unsigned b) < assert(a >1); while (a unsigned p = a; do < unsigned p2 = p * p; if (p2 > b) break; p = p2; > while (true); if (b % p != 0) break; b /= p; > return b == 1; >

Определить, является ли число степенью любого натурального числа

Author24 — интернет-сервис помощи студентам

Степень числа
Дано натуральное число, большее 1. Определить, является ли оно степенью любого натурального числа. Считается, что показатель степени больше 1.
Формат входных данных
Вы вводите количество контрольных примеров N, затем через пробел N (N≤10000) чисел, каждое из которых не превышает 1000000000.
Формат результата
Ви виводите 1, если число является степенем та 0 в другом случае.

Входные данные
3 4 5 27
Результат работы
101

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

Является ли число n естественной степенью некоторого натурального числа
Пользователем вводится натуральное число n. Программа должна выяснить, является ли число n.

Определить, является ли натуральное число степенью другого натурального числа
Очередная задачка из раздела С++. Собственно, вся суть в заголовке. При желании можно выдать не.

Проверить является ли заданное пользователем натуральное число степенью натурального числа
проверить, является ли заданное пользователем натуральное число степенью натурального числа в.

Алгоритм определения является ли натуральное число степенью какого-либо натурального числа
Помогите на гос.экзамене. Т.е. Вводится одно натуральное число, а выводом должно быть — число.

Эксперт функциональных языков программированияЭксперт Python

36619 / 20342 / 4225
Регистрация: 12.02.2012
Сообщений: 33,681
Записей в блоге: 13

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def is_power_of(n): if n==1: return 1 i=2 while(i*in): if n%i==0: k=n//i while(k>1): if k%i==0: k=k//i else: break if k==1: return 1 i+=1 return 0 def task(): n=int(input()) lst=map(int,input().split(" ")) print(*list(map(is_power_of,lst))) task()

Status 418

Эксперт Python

4578 / 2345 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
Catstail, «вангую» по времени не пройдет

Эксперт функциональных языков программированияЭксперт Python

36619 / 20342 / 4225
Регистрация: 12.02.2012
Сообщений: 33,681
Записей в блоге: 13
eaa, да, алгоритм небыстрый
Status 418

Эксперт Python

4578 / 2345 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
степени могут быть от 2 до 29. достаточно их перебрать чтобы определить is_power_of.
705 / 351 / 104
Регистрация: 09.02.2018
Сообщений: 798

1 2 3 4 5
def is_power_between2_29(n): for i in range(2, 30): if int(n ** (1 / i)) ** i == n: return True return False

Эксперт Python

8219 / 4338 / 1838
Регистрация: 27.03.2020
Сообщений: 7,162
КулХацкеръ, только range(2, 34)
705 / 351 / 104
Регистрация: 09.02.2018
Сообщений: 798

Gdez, почему?

>>> int(math.log2(1000000000)) + 1
30

Status 418

Эксперт Python

4578 / 2345 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
можно так, если по времени пройдет. и хватит ли точности у float.

Эксперт Python

8219 / 4338 / 1838
Регистрация: 27.03.2020
Сообщений: 7,162

КулХацкеръ, 10^10 насчитал

Добавлено через 35 секунд
Если 9, то верно

Эксперт функциональных языков программированияЭксперт Python

36619 / 20342 / 4225
Регистрация: 12.02.2012
Сообщений: 33,681
Записей в блоге: 13

Лучший ответ

Сообщение было отмечено SashaBrine как решение

Решение

Еще один алгоритм определения степени:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def isPower(n): k=2 d={} while(n>1): if n%k==0: if d.get(k)==None: d[k]=1 else: d[k]+=1 n=n//k; else: k+=1 t=min(d.values()) for a in d.values(): if a%t !=0: return False return True

Status 418

Эксперт Python

4578 / 2345 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
корень бы я вычислял бин.поиском и сразу же целочисленный.
Регистрация: 05.11.2019
Сообщений: 33
Catstail спасибо
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Найти и вывести первое число большее n (вводится), которое является степенью натурального числа 2.9
Найти и вывести первое число большее n (вводится), которое является степенью натурального числа.

Определить, является ли число N степенью числа 3
Доброго времени суток. Я начинающий программист) В общем задача такая составить программу: .

Определить, является ли число Х степенью числа 2
Является ли число Х степенью числа 2(ЙЕС или НОУ)? Например числа 8,2,32- Являются, а 5,7,6-нет.

Определить: является ли заданное число степенью числа 3
Определить: является ли заданное число степенью числа 3

Определить является ли заданное число степенью числа 5
первая задача 1. Даны последовательность вещественных чисел a1,a2,…,a15, упорядоченная по.

Определить, является ли натуральное число N степенью числа 3
здравствуйте! Помогите, пожалуйста. Задание в windows forms, не понимаю в чем моя ошибка. .

Определить, является ли число степенью другого числа
Составить подпрограмму, определяющую , является ли число степенью другого числа.

Или воспользуйтесь поиском по форуму:

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

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