e-olymp 842. Разложение на простые множители

Условие задачи
Вывести представление целого числа [latex] n [/latex] в виде произведения простых чисел.

Входные данные
Единственное число [latex] n [/latex] [latex] (2 ≤ n ≤ 2^{31} — 1). [/latex]

Выходные данные
Вывести список простых множителей в порядке не убывания, разделённых знаком [latex] «*» [/latex] .

Тесты

Входные данные	Выходные данные
[latex]30[/latex]	[latex]235[/latex]
[latex]16[/latex]	[latex]222*2[/latex]
[latex]5[/latex]	[latex]5[/latex]
[latex]12[/latex]	[latex]223[/latex]
[latex]7[/latex]	[latex]7[/latex]
[latex]144[/latex]	[latex]22223*3[/latex]

Код программы

#include <iostream>
using namespace std;
 
int main() {
    long long numb, divisor = 2;
    cin >> numb;
    while (divisor*divisor <= numb)
    {
        if (numb%divisor == 0)
        {
            cout << divisor;
            numb = numb / divisor;
            cout << '*';
        }
        else if (divisor == 2) divisor = 3;
        else divisor = divisor + 2;
    }
    cout << numb;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long numb, divisor = 2;

cin >> numb;

while (divisor*divisor <= numb)

{

if (numb%divisor == 0)

{

cout << divisor;

numb = numb / divisor;

cout << '*';

}

else if (divisor == 2) divisor = 3;

else divisor = divisor + 2;

}

cout << numb;

return 0;

}

Решение задачи
Пока наше число больше либо равно divisor*divisor выполняется:

Если numb делится нацело на divisor, мы выводим наш делитель, следовательно numb делится на divisor;
В противном случае:

Если divisor равен $2$, то присваиваем ему значение $3$ и повторяем;
В другом случае увеличиваем его на $2$;

Таким образом перебираются $2,3$ и $5$, которые являются делителем для всех чисел.

Ссылки

Задача на сайте E-olymp
Код решения в Ideone

Related Images:

Похожее

3 thoughts on “e-olymp 842. Разложение на простые множители”

Мазурок Игорь Евгеньевич says: 02/05/2018 at 11:21
- Пожалуйста, определитесь с отступами. С сентября занимаемся. Уже бы пора.
- Не очень удачные именования. Исходите из этого: In division, the dividend is divided by the divisor to get a quotient.
- Просмотрите внимательно, что у Вас получилось и поправьте всякие & lt
- Тип данных выбран излишне большим
- Подумайте, как избавиться от лишнего цикла. Это сократит программу почти вдвое. Ведь это все накручено только чтобы определить нужна ли *?
Войдите, чтобы ответить
- Иван Василевский says: 04/05/2018 at 18:24
  
  Игорь Евгеньевич, исправил. Теперь вместо 3-х циклов всего 1.

Хорошо, только соедините 11 и 113ю строку в одной команде печати.
У меня тоже похоже получалось:

#include <iostream>
int main() {
    unsigned int n;
    std::cin >> n;
    const unsigned int max = n;
    for(unsigned int i = 2; i*i <= max; )
        if (n % i == 0) std::cout << i << (1 == (n /= i)? "" : "*");
        else ++i;
    if (n > 1) std::cout << n;
    return 0;
}

unsigned int n;

std::cin >> n;

const unsigned int max = n;

for(unsigned int i = 2; i*i <= max; )

if (n % i == 0) std::cout << i << (1 == (n /= i)? "" : "*");

else ++i;

if (n > 1) std::cout << n;

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

Для отправки комментария вам необходимо авторизоваться.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olymp 842. Разложение на простые множители

Related Images:

Понравилось это:

Похожее

3 thoughts on “e-olymp 842. Разложение на простые множители”

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

Related Images:

Share this:

Понравилось это:

Похожее

3 thoughts on “e-olymp 842. Разложение на простые множители”

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