Найти простые множители в C++


Пожалуйста, ознакомьтесь с настоящим Кодексом.

#include <iostream>
#include <vector>

bool is_prime(int x)
{
    int flag = 1;
    for (int i = 2; i <= x/2; i++)
    {
        if (x % i == 0)
        {
            flag = 0;
            break;
        }
    }
    if (flag == 1)
    {
        return true;
    }
    else if (flag == 0)
    {
        return true;
    }
}

void find_prime_factors(int n, std::vector<int>& vec)
{
    int val = n;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime(i))
        {
            while (val % i == 0 && val != 1)
            {
                vec.push_back(i);
                val = val/i;
            }
            if (val == 1)
            {
                break;
            }
        }
    }
}

int main()
{
    int n;
    std::cout << "Enter number\n";
    std::cin >> n;
    std::vector<int> prime_factors;
    find_prime_factors(n, prime_factors);
    std::cout << "Prime Factors of " << n << ":\n";
    for (int i = 0; i < prime_factors.size(); i++)
    {
        std::cout << prime_factors[i] << " ";
    }
    std::cout << "\n";
}


2655
11
задан 11 апреля 2018 в 01:04 Источник Поделиться
Комментарии
2 ответа

Вашей программе есть ошибка. is_prime возвращает true во всех возможных return ситуациях. Вы не замечаете, потому что ваш премьер-факторов уже использовать хороший отель Премьер-факторы, которые мы проверим позже. Вот краткий список улучшений первым:


  1. return condition вместо if condition return true; else return false;

  2. return рано.

  3. Использовать соответствующие типы возвращаемых значений.

  4. Модифицировать алгоритмы.

Теперь давайте сосредоточимся на ошибках первого.

is_prime

Во-первых, очевидное: оба return заявления только вернуться true. Однако, есть некоторые улучшения, мы можем применить. Во-первых, если два условия являются эксклюзивными и охватывают весь диапазон возможных условий использования if/else без второго, если:

if (flag == 1)
{
return true;
}
else // no if here!
{
return true;
}

Обратите внимание, что это все еще содержит ошибки. Это подводит нас к следующему благоустройству: вместо

if (condition) {
return true;
} else {
return false;
}

просто return condition:

return (flag == 1);

Отметим, что это уже полностью удаляет ошибки. Но мы можем пойти дальше. flag сама по себе представляет источник возможных ошибок. Мы могли случайно использовать flag = 3 (которые могут быть опосредованы bool flag) или забыли установить flag (что можно проверить статический анализ).

Но мы не нужны flag. Либо мы break петли (и, следовательно, flag = 0) и мы вернемся falseили мы не будем и вернуть true. Это прекрасная возможность использовать рано returnС:

bool is_prime(int x)
{
for (int i = 2; i <= x/2; i++)
{
if (x % i == 0)
{
return false;
}
}
return true;
}

Есть два способа оптимизации, которые остались для тренировки. Во-первых, нам не нужно проверять каждый iно только каждый второй. Если x % 2 != 0тогда x % i != 0 для всех даже i. Кроме того, для любой пары факторов \$АВ=х\$ держит \долл\Ле\ Б$ и, следовательно, \долларов\Ле \функция sqrt{х}\$. Обе оптимизации оставлено в качестве упражнения.

find_prime_factors

Сейчас мы посмотрим на 3,. "использовать соответствующие типы возврата". Результат функции-это вектор. Ничто в его интерфейс позволяет пользователю предоставить уже заполненный вектор, например:

std::vector<int> example = {1,2,3,4,5};
find_prime_factors(10, example); // whoops!

Поэтому вместо того, чтобы иметь find_prime_factors вернуть его результат:

std::vector<int> find_prime_factors(int n)
{
int val = n;
std::vector<int> result;
for (int i = 2; i <= n; i++)
{
if (is_prime(i))
{
while (val % i == 0 && val != 1)
{
result.push_back(i);
val = val/i;
}
if (val == 1)
{
break;
}
}
}
return result;
}

Далее мы сосредоточимся на алгоритме. Как вы заметили, find_prime_factors работал, хотя is_prime нарушается. Почему?

Когда вы делите число на наименьшее главным фактором, следующим номером, что позволит разделить новое число должно быть главным фактором. Давайте попробуем его по руке:

$$
всегда \begin{выравнивания}
420 &= 2\cDOT на 2 \cDOT на 105 &\текст{ следующий фактор } 3 \\
&= 2\cDOT на 2 \cDOT на 3 \cDOT на 35 &\текст{ следующий фактор -} 5 \\
&= 2\cDOT на 2 \cDOT на 3 \cDOT на 5 \cDOT на 7 &\текст{ следующий фактор } 7 \\
&= 2\cDOT на 2 \cDOT на 3 \cDOT на 5 \cDOT на 7 \cDOT на 1
\конец{выравнивания}
$$
Нам не нужен is_prime проверить на всех:

std::vector<int> find_prime_factors(int n)
{
int val = n;
std::vector<int> result;
for (int i = 2; i <= n; i++)
{
while (val % i == 0 && val != 1)
{
result.push_back(i);
val = val/i;
}
if (val == 1)
{
break;
}
}
return result;
}

Кроме того, мы можем остановиться, как только i > val, потому что на тот момент val == 1.
На самом деле, мы можем избавиться от val вообще и просто изменить n:

std::vector<int> find_prime_factors(int n)
{
std::vector<int> result;
for (int i = 2; i <= n; i++)
{
while (n % i == 0)
{
result.push_back(i);
n /= i;
}
}
return result;
}

В какой-то момент n == i и n /= i даст n == 1, так что мы не придется беспокоиться о бесконечном цикле. Этот алгоритм также известен как судебный отдел. Обратите внимание, что мы также можем применить для оптимизации даже цифры (слева в качестве другого упражнения).

Есть и другие оптимизации, которые можно применить:


  • зарезервировать память заранее (а числа $\Н\$ может иметь не более \$\log_2 П\$ факторов, поэтому std::vector::reserve могут быть использованы)

  • используйте методы, которые дает как частное и делитель одновременно (очень конкретной платформы).

Для веселой тренировки, вы можете переписать его с итераторами в виду:

template <typename OutputIt> OutputIt(int n, OutputIt out) {
// exercise
}

Обратите внимание, что это несколько излишним, поскольку n будет содержать не более 64 главных факторов, если ваш int использует 64 бита.

Нижняя линия

Проверьте все свои функции. is_prime содержит неприятный баг. Другие, чем, что ваш код хорошо структурирован, не использовать using namespace и было легко читать.

25
ответ дан 11 апреля 2018 в 02:04 Источник Поделиться

Когда я писал свой ответ, я думал, что это было по другому принято отвечать. После перечитывания принято отвечать, я понял, что алгоритм, представленный в обеих одинаковы. Я решил оставить мой ответ здесь, так как объяснение и изложение разное.

Этот ответ фокусируется на коротком простое решение проблемы.

#include <iostream>

int main()
{
int n;
std::cout << "Enter number\n";
std::cin >> n;
for (int p = 2; n > 1 && p <= n; p++)
{
while (n % p == 0)
{
std::cout << p << " ";
n /= p;
}
}
std::cout << n << "\n";
}

В решении, мы видим, никакого упоминания какого числа, кажется, мы тестируем каждого значения Р в интервале от 2 до n, и это правильно. Мы. Однако, результат всегда список простых чисел? Почему?

Когда программа начинается, и вы вводите 420, он пытается "2"...

n    p    output       n'    p'   description
420 2 2 210 2 2 goes into 420
210 2 2 2 105 2 2 goes into 210
105 2 2 2 105 3 2 doesn't go into 105 move to next 'prime'
105 3 2 2 3 35 3 3 goes into 105
35 3 2 2 3 35 4 3 doesn't go into 35 move to next 'prime'
35 4 2 2 3 35 5 4 doesn't go into 35 move to next 'prime'
35 5 2 2 3 5 7 5 5 goes into 35
7 5 2 2 3 5 7 6 5 doesn't go into 7 move to next 'prime'
7 6 2 2 3 5 7 7 6 doesn't go into 7 move to next 'prime'
7 7 2 2 3 5 7 1 7 7 goes into 7, and we terminate loop

Итак, мы на самом деле пытаемся все числа от 2..7, но, почему 4 и 6 не получить удар, потому что мы уже сняли 2 и 3 в качестве факторов, ранее. В общих чертах, все не Прайм версии p никогда не получить удар, потому что мы уже сняли, связанных с основными факторами ранее.

Я положил std::cout << n << "\n" В конце, чтобы показать остаточную стоимость n. Как правило, это будет просто 1. Однако, это полезно для обработки краевых условий, когда пользователь вводит 0, 1 или отрицательное число. Мы просто возвращаемся ввода пользователя обратно к ним, а не ничего не показывая их.

bruglesco предложил изменяя конечное состояние p*p <= nт. е.

  for (int p = 2; n > 1 && p*p <= n; p++)

Несмотря на это изменение, очень проста, она оптимизирует алгоритм существенно значение для входного как 97 мы испытываем только от 2..9, чтобы понять, что нет смысла проверять дальше. Это делает последнюю строку я добавил еще актуален, так как уже не на краю состояние, но, показывает последний Прайм.

4
ответ дан 11 апреля 2018 в 09:04 Источник Поделиться