Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.03.2013, 22:02   #1
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию Представить n в виде произведения простых чисел

Нужно найти каждое значение p^a, если дано n. Помогите, пожалуйста.
Изображения
Тип файла: jpg 1.jpg (3.1 Кб, 84 просмотров)
akademochka вне форума Ответить с цитированием
Старый 21.03.2013, 00:40   #2
_Bers
Старожил
 
Регистрация: 16.12.2011
Сообщений: 2,329
По умолчанию

http://www.programmersforum.ru/showthread.php?t=34061
_Bers вне форума Ответить с цитированием
Старый 21.03.2013, 07:41   #3
Bugrimov
C/C++, Java
Участник клуба
 
Аватар для Bugrimov
 
Регистрация: 28.03.2012
Сообщений: 1,680
По умолчанию

Интересное задание Есть ли наработки?
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости"
Сложность - враг простоты и удобства!

Последний раз редактировалось Bugrimov; 21.03.2013 в 07:54.
Bugrimov вне форума Ответить с цитированием
Старый 21.03.2013, 09:00   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

а что в этом задании интересного/сложного?
берём первое простое число (2) делим исходное n на него, пока нацело делится, получили p1 (это двойка) и a1 (это то, сколько раз смогли разделить число N на p1 без остатка).
в цикле повторяем, пока N>1
взять следующее простое число Pi
делить N на это простое число, пока делится, получать ai
конец цикла

примечание. Если число N не кратно очередному простому числу Pi, тогда ai получается нулевое, и этот сомножитель пропускать.

всё.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 21.03.2013, 19:37   #5
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию

Код:
int x,a,b; 
 cin >> x; 
 while( x != 1) 
 { 
 for(a=2;(x%a) != 0;a++){} 
 for(b=0;(x%a) == 0;b++){x=x/a;} 
 cout << a << " " << b << endl; 
 }
НО эта реализация превышает лимит времени
akademochka вне форума Ответить с цитированием
Старый 21.03.2013, 20:43   #6
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Код:
int x, a = 2, b; 
cin >> x; 
while( x != 1)  { 
    for(;x / a && x % a; ++a) {} 
    for(b = 0; !(x % a); ++b) {
        x /= a;
    } 
    cout << a << " " << b << endl; 
}
Небольшое ускорение.

Цитата:
просто и красиво
Не так уж просто и красиво
Не проходит последний тест на АЦМП:
Код:
#include <math.h>
#include <fstream>

main()
{
    std::fstream I("input.txt"), O("output.txt", 2);
    int x, a = 2, t = 0; 
    I >> x; 
    while (x != 1) { 
        while (x / a && x % a) {
            ++a;
        } 
        while (!(x % a)) {
            x /= a;
            if (t) {
                O << "*";
            }
            t = 1;
            O << a;
        } 
    }
}
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 21.03.2013 в 21:13.
BDA вне форума Ответить с цитированием
Старый 21.03.2013, 21:04   #7
Bugrimov
C/C++, Java
Участник клуба
 
Аватар для Bugrimov
 
Регистрация: 28.03.2012
Сообщений: 1,680
По умолчанию

BDA просто и красиво.... Учусь, мотаю на ус...
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости"
Сложность - враг простоты и удобства!
Bugrimov вне форума Ответить с цитированием
Старый 22.03.2013, 11:42   #8
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию

Код:
for(int i = 2; i * i <= x; i++)
{

if (x % i == 0) 
while(x % i == 0) x /= i;}
только это сразу для p^a, а не отдельно выводить p и a.
Это не работает, можно как-то исправить?
akademochka вне форума Ответить с цитированием
Старый 22.03.2013, 11:55   #9
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Код:
for(int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
        int c = 0;
        while(x % i == 0) {
            x /= i;
            ++c;
        }
        cout << i << " " << c << endl;
    }
}
Может так? Не проверял (далеко от компьютера).
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 22.03.2013, 13:40   #10
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

BDA, респект, снимаю шляпу!
спасибо за код. Получил истинное наслаждение!



"чудо" данного алгоритма в том, что делители незачем проверять на простоту.
Сам тот факт, что мы на предыдущих шагах делим исходное число (сначала на 2, потом на 3) уже гарантирует, что делители будут ПРОСТЫМИ числами!
Алилуйя!!
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
ЦИКЛЫ (паскаль) - представить N в виде суммы факториалов натуральных чисел, содержащей наименьшее число слагаемых Katya20 Помощь студентам 7 09.01.2012 01:21
Можно ли число N представить в виде сумы двух квадратов натуральных чисел? Dima170792 Помощь студентам 2 24.06.2011 08:53
всякое целое число можно представить в виде трех простых stasey91 Помощь студентам 3 14.04.2011 21:44
Дано натуральное число n. Можно ли представить его в виде суммы двух квадратов натуральных чисел? Сеня Помощь студентам 3 29.01.2009 01:17