Доступ к неинициализированному значению, наиболее вероятно в векторе

Question

Я делаю упражнение, где мне нужно найти положительные целые числа p и q, которые являются факторами другого натурального числа n. Следуя формуле n=pq*q, где p - это число squarefree .

Однако для некоторых экземпляров программы мой компилятор обнаруживает ошибку памяти, говорящую о том, что я обращаюсь к неинициализированному значению.

Логика, которую я попробовал, заключается в следующем. Во-первых, я взял число, которое необходимо учесть (назовите его n). Далее я нашел все факторы числа n и поместил их в вектор. После этого проверьте, является ли каждый элемент этого вектора squarefree . Если true, поместите элемент в другой вектор (вектор свободных от квадратов множителей числа n). После этого просмотрите каждый элемент вектора факторов без квадратов и решите уравнение q=sqrt(n/p), где p - коэффициент без квадратов из вектора. Кроме того, я проверяю условие if(int(sqrt(n/p))==sqrt(n/p)), поскольку квадратный корень должен быть положительным целым числом.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Function that checks if the number is squarefree

bool isSquareFree(int n)
{
    if (n % 2 == 0)
        n = n / 2;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i <= sqrt(n); i += 2)
    {
        if (n % i == 0)
        {
            n = n / i;
            if (n % i == 0)
                return false;
        }
    }
    return true;
}

void Factorise_the_number(int n, int &p, int &q)
{
    if (n <= 0)
        return 0;
    vector<int> factors(0); // vector of factors
    vector<int> sqfree_factors(0); // vector of squarefree factors
    int sqfree_number; // the number "p"
    int squared; // is essentially the number "q"

    for (int i = 1; i <= n / 2; i++)
    {
        if (n % i == 0)
            factors.push_back(i); // takes all factors of the number "n"
    }

    for (int i = 0; i < factors.size(); i++)
    {
        if (isSquareFree(factors.at(i)))
            sqfree_factors.push_back(factors.at(i));
    } // checks if each factor is squarefree. if yes, put it in a separate vector

    for (auto x : sqfree_factors)
    {

        if (int(sqrt(n / x)) == sqrt(n / x))
        { // if true, we found the numbers
            squared = sqrt(n / x);
            sqfree_number = x;
            break;
        }
    }

    p = sqfree_number;
    q = squared;
}

int main()
{

    int n, p = 0, q = 0;
    cin >> n;

    Factorise_the_number(n, p, q);
    cout << p << " " << q;

    return 0;
}

Например, моя программа работает, если я ввожу число 99, но не работает, если я ввожу 39. Кто-нибудь может дать какое-либо понимание?

Спасибо!

Answer 1

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

Давайте посмотрим на это вместе.Сначала он пытается найти все факторы и находит 1, 3 и 13: это выглядит нормально.

Затем он проверяет, является ли каждое из этих чисел квадратичным, и все они равны: это также выглядит правильно.

Затем он проверяет, удовлетворяет ли какой-либо из квадратичных факторов равенству, которое вы ищете.Ни один из них не делает (39 - 3 x 13, нет никакого способа, которым это может содержать квадратный фактор).Это означает, что if (int(sqrt(n / x)) == sqrt(n / x)) никогда не соответствует действительности, и этот блок никогда не запускается.Каковы значения sqfree_number и squared на тот момент?Это никогда не инициализируется.Использование неинициализированных значений приводит к «неопределенному поведению», то есть ваша программа может делать все что угодно.В этом случае p и q содержат случайные значения.

Как это можно исправить?Учтите это: если n не удовлетворяет вашему уравнению, то есть оно не может быть выражено как pq * q, что именно должна выводить программа?Будет ли ваш вывод, как сейчас, когда-либо иметь смысл?Нет. Это означает, что вы должны изменить свою программу так, чтобы она охватывала случай, который вы не рассматривали.

Можно добавить bool found = false; непосредственно перед вашим последним циклом for.Когда вы найдете факторы, прежде чем нарушать, установите эту переменную на true.Затем, вне цикла, проверьте: это true?Тогда вы можете вернуть правильные значения.Но если это все еще false, это означает, что равенство не выполняется, и вы не можете вернуть правильные значения.Вы должны найти способ сообщить об этом вызывающей стороне (это ваша функция main), чтобы она могла напечатать соответствующее сообщение.

И как вы можете сообщить об этом?В общем, вы можете изменить Factorise_the_number (кстати, имя функций должно начинаться со строчной буквы; заглавные буквы обычно используются для классов), чтобы вернуть bool.Или вы можете использовать хитрость: вернуть специальное значение для p и q, которое не может быть результатом вычисления.Нравится -1.Затем, перед печатью, проверьте: если значения -1, это означает, что число не может быть выражено как pq * q.