Wrote a program that would decompose any integer into factors.

#include <iostream> #include <cstdlib> using namespace std; bool isLCM (int num, int denum); int fill_array(int &num, int *arr); int main() { setlocale(LC_ALL,"rus"); int num; int *arr_of_denums = new int [1]; // массив для заполнения cin >> num; // в переменную n будет возвращен размер получившегося массива с делителями int n = fill_array(num, arr_of_denums); // вывод разложенного числа num на экран; for (int i = 0; i < n; i++) { if ( i == n - 1) cout << arr_of_denums[i]; //проверка на последний делитель // если он последний, то ненадо после него ставить '*' else cout << arr_of_denums[i] << " * "; } delete []arr_of_denums; return 0; } // функция принимает число num и делитель denum // в теле идет проверка на делимость num на denum bool isLCM(int num, int denum) { if ( num%denum == 0 ) return true; else return false; } // функция принимает число num и указатель на массив для заполнения arr // массив заполняется делителями числа num // и возвращает размер заполненного вектора int fill_array (int &num, int *arr) { int denums[] = { 2, 3, 5, 7, 11}; //массив делителей для числа num int j = 0; for (int i = 0; i < 5;) { if (isLCM(num, denums[i])) { arr[j] = denums[i]; num = num/denums[i]; j++; } else i++; } return j; }

the program works, everything outputs correctly, but there is one thing: it does not fully decompose. I tried to decompose 1824, she derived 2 ^ 5 * 3, although the total decomposition would be 2 ^ 5 * 3 * 19. Actually, how to make her deduce that same 19? And at the same time, please rate how the code is written. I'm just learning, I want to write not only correctly, but also understandable :)

  • If decomposition is of interest - see, for example, this question - Harry

2 answers 2

If you really want to consider only dividers in the loop, specified in the denums array, then after completing the cycle you need to add to the arr array what remains of the num number (provided that num does not equal 1 at the end). In the example with the decomposition of 1824, this will be your 19.

Only the arr_of_denums array is arr_of_denums to you with a size of only 1. So more than one number in arr_of_denums cannot be entered in any way. Why do you select such a small array?

If you abandon the "bare" array and use std::vector instead, then the implementation of your algorithm may look like

 void fill_array(int num, std::vector<int> &arr) { const int denums[] = { 2, 3, 5, 7, 11 }; //массив делителей для числа num for (int i = 0; i < sizeof denums / sizeof *denums;) { if (isLCM(num, denums[i])) { arr.push_back(denums[i]); num /= denums[i]; } else i++; } if (num != 1) arr.push_back(num); }

and challenge

 ... std::vector<int> arr_of_denums; fill_array(num, arr_of_denums); // вывод разложенного числа num на экран; for (int i = 0; i < arr_of_denums.size(); i++) { ...

Or even

 std::vector<int> fill_array(int num) { const int denums[] = { 2, 3, 5, 7, 11 }; //массив делителей для числа num std::vector<int> arr; for (int i = 0; i < sizeof denums / sizeof *denums;) { if (isLCM(num, denums[i])) { arr.push_back(denums[i]); num /= denums[i]; } else i++; } if (num != 1) arr.push_back(num); return arr; }

and challenge

 ... std::vector<int> arr_of_denums = fill_array(num); // вывод разложенного числа num на экран; for (int i = 0; i < arr_of_denums.size(); i++) { ...

Separately, it can be noted that the manipulations you perform are practically one-to-one correspond to the simplest algorithm for factoring the number.

 unsigned n = 1824; unsigned d = 2; while (d < n) if (n % d == 0) { cout << d << " "; n /= d; } else ++d; if (n != 1) cout << n << " "; cout << endl;

Only this algorithm does not need an array of simple dividers prepared in advance - it finds them by itself (albeit inefficiently). Maybe your denums array denums completely useless? Or is this the job?

  • As far as I understood, I created a dynamic array, which will be expanded as needed, and I wrote 1 from there, if I could, I left the brackets empty, but the compiler swears. I tried to make your version, added at the end of the function line "++ j;" and "arr [j] = num;" (sorry, I don’t know how to make an example of a code in a comment), but the program was displaying garbage instead of the required number - niki4iko
  • @ niki4iko: Arrays in C ++ never expand themselves "as needed." You need to either manually expand it yourself, or (better) just use std::vector . And you need to add arr[j] = num; ++j; arr[j] = num; ++j; . In that order, and not vice versa. - AnT
  • I tried std :: vector, but I didn’t rummage through the internet, I didn’t find how to correctly pass it and fill in the function. By this, I decided to use the usual array. Do not tell me how to do with the vector? - niki4iko
  • an array of denums is really useless, thank you) there is no job, this is my imagination out of my head :) - niki4iko

To begin with, the program has an undefined behavior, as there is an attempt to access memory outside the dynamically allocated array. In this offer

 int *arr_of_denums = new int [1]; // массив для заполнения

An array consisting of only one element is allocated. However, in the fill_array function in a loop

  for (int i = 0; i < 5;) { if (isLCM(num, denums[i])) { arr[j] = denums[i]; ^^^^^^ num = num/denums[i]; j++; }

there is an attempt to access 5 elements of the array.

Instead of manually allocating a dynamically array, it is much safer and easier to use the standard container std::vector .

As for the programming style. This function has an incomprehensible interface.

 int fill_array(int &num, int *arr);

What is the point of passing the variable num by reference?

It is more logical to declare the parameters in the reverse order.

 int fill_array( int *arr, int num);

A function with an incomprehensible name isLCM can be generally written in one line.

 bool isLCM(int num, int denum) { return num % denum == 0; }

The question arises: is it necessary for a single arithmetic built-in operation to determine the entire function?

The program uses "magic" numbers, such as the number 5 in this cycle.

 for (int i = 0; i < 5;) {

Well, the algorithm itself suffers from the limitation of the number of possible prime numbers. Therefore, the prime number 19 you can not get. To do this, you need to redefine the local array, which is actually completely redundant.