string result;
string M="1", S="1";
bool factors=true, power=true;
while (factors) {
M++;
result=M;
power=true;
while (power) {
S++;
result=result*M;
if (result>N) {
if (S=="2") {
cout << N << " may be prime"; //N нельзя разложить в степень другого
factors=false;
power=false;
} else {
power=false;
S="1";
}
}
if (result==N) {
power=false;
factors=false;
cout << N << " is not prime N=" << M << "^" << S; //N=M^S
}
}
}
является ли число степенью другого
Мне дано очень большое натуральное число N. Предложите мне быстрый алгоритм, который дает ответ на вопрос: можно ли выразить N через степень другого, т.е. N=m^s, где m и s - тоже натуральные.
Посчитать логарифм N по основанию m. :)
P.S. Что понимать под "очень большим натуральным числом", кстати? Насколько большое?
P.S. Что понимать под "очень большим натуральным числом", кстати? Насколько большое?
Цитата: Alexander92
Посчитать логарифм N по основанию m. :)
Для этого надо перебирать все значения m до квадратного корня из N и делать m*m*m*m.. и так s раз. Можно ли этот алгоритм как-то быстрее? Например, увеличивать не линейно, а квадратично.
Цитата: Alexander92
P.S. Что понимать под "очень большим натуральным числом", кстати? Насколько большое?
Число должно иметь более 1024 разрядов.
Бросилось в глаза:
Цитата: Charley
Число должно иметь более 1024 разрядов.
а потом почему то обратил внимания на местожительство автора... суровые челябинские программисты
Цитата:
Гуго́л (от англ. googol) — число, в десятичной системе счисления изображаемое единицей со 100 нулями:
10^100 = 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000.
Гугол больше, чем количество частиц в известной нам части Вселенной, которых, по разным оценкам, насчитывается от 10^79 до 10^81
10^100 = 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000.
Гугол больше, чем количество частиц в известной нам части Вселенной, которых, по разным оценкам, насчитывается от 10^79 до 10^81
Цитата: Charley
Число должно иметь более 1024 разрядов.
Прошу прощения, 200 разрядов. Т.к. это нужно для алгоритма Миллера, а наибольшее известное простое число имеет 200 разрядов.
Цитата: Charley
...а наибольшее известное простое число имеет 200 разрядов.
Это я с факторизацией напутал, в-общем это надо для реализации RSA-200
Цитата: Charley
Прошу прощения, 200 разрядов. Т.к. это нужно для алгоритма Миллера, а наибольшее известное простое число имеет 200 разрядов.
Эмм... я конешно математик никудышный, но сдается, что у гугля 100 нулей после 1 это и есть количество разрядов. А что бы получить 200 разрядов надо гуголь в степень гуголя возвести.
Сам по себе гуголь это просто ибаниститчески большое число, а уж ежели в степень то вообще ппц.
Пусть каждая частица будет хранить единицу от этого числа, тогда понадобиться только для его хранения гуголь вселенных вещества.
Цитата:
встречаются два рыбака: первый говорит:" вчера поймал сома,бросил в багажник, хвост не влез так домой и поехал. Второй"я вчера щуку поймал с меня ростом-распорол живот, а там подсвечник и свечи горят." Первый"слышь я хвост в багажник уберу , но ты свечи затуши"
Я опять возвращаюсь к вопросу: как быстро узнать представимо ли N в виде N=M^S.
Я сделал с помощью простого перебора M и S:
Но этот алгоритм работает очень медленно: например, для числа с 6 разрядами он работает около 3 минут.
Я сделал с помощью простого перебора M и S:
Код:
Но этот алгоритм работает очень медленно: например, для числа с 6 разрядами он работает около 3 минут.
цикл разверните . M не с единицы , а с корня S степени из N до 2 .
S перебирать только по простым числам .
S перебирать только по простым числам .
Если число является степенью другого числа, то оно должно делиться и на само число (M==N^S ==> M%N==0), что существенно упрощает задачу. Если та так пытаешься проверить N на простоту - то есть много быстрых и оптимальных алгоритмов.