Trying to find the most common factor

[Gondel516]

So, I am practicing for a school competition coming up, and I am stumped on this problem, it just simply won't work, what am I doing wrong?

It is supposed to find the most common factor, my test numbers are 32 and 27, which should give 2 and 3.

#include <iostream>
using namespace std;

int main(){
    int input;
    cout << "What number?";
    cin >> input;
    int factorAmount[input];
    int temp = 0;
    if(input > 100 || input < 1){
        cout << "This number is not in the specified paramaters. Try again.\n";
        return 6;
    }else{
        for(int factor = 1; factor<input; factor++){
            while(input != 1){
                while(input%factor==0){
                factorAmount[factor]++;
                }
            
                }
            }
            
        }
        for(int i = 0; i < input; i++){
            temp = factorAmount[i];
            
        }
        cout << temp;
    }

[JLBorges]

#include <iostream>

int main()
{
    int number ;
    std::cout << "number? " ;
    std::cin >> number ;

    int most_common_factor = number ;
    int max_frequency = 0 ;

    for( int factor = 2 ; factor <= number ; ++factor )
    {
        int frequency_of_this_factor = 0 ;
        while( number%factor == 0 )
        {
            ++frequency_of_this_factor ;
            number /= factor ;
        }

        if( frequency_of_this_factor > max_frequency )
        {
            most_common_factor = factor ;
            max_frequency = frequency_of_this_factor ;
        }
    }

    // note: the smallest most common factor in case of ties
    // eg. if the number is 36 (2x2x3x3), prints out 2
    std::cout << "most common factor: " << most_common_factor << '\n' ;
}

[Gondel516]

I need it to print NONE, when two factors tie. What would I need to do, and if you could, what was wrong with my original code? Not that there was anything wrong with yours, it works perfectly, I am just trying to learn from my mistakes

[JLBorges]

> what was wrong with my original code?

1. This is not allowed in C++ int factorAmount[input];
The size of an array must be a constant known at compile time.
http://coliru.stacked-crooked.com/a/04c7865cab2cdefc

The solution is extremely simple: use std::vector https://cal-linux.com/tutorials/vectors.html

Note: If the compiler that is being used is a GNU compiler (or a GNU-compatible compiler), by default it does not conform to standard C++.
We need to force standard conformance with the options -std=c++14 -pedantic-errors

2. Ignoring 1. for the moment (say we are compiling the popular non-standard Linux dialect),
with int factorAmount[input]; the numbers in the array are not initialised.
(This will engender undefined behaviour when we try to increment the number.)

3. This while(input%factor==0) results in an infinite loop (a loop that never ends) if input is divisible by factor.
(the value of input is not modified)
Also note that the value of factor starts at one, and every number is evenly divisible by one ad infinitum.


> I need it to print NONE, when two factors tie. What would I need to do

Something like this; the logic is based on your original approach to the problem.
The code is commented (though not tested); the comments should aid in understanding the logic

#include <iostream>
#include <vector>

int main()
{
    int number ;
    std::cout << "number [0,100]:? " ;
    std::cin >> number ;
    std::cout << "number: " << number << ' ' ;

    if( number < 2 || number > 100 )
    {
        std::cerr << "the number is out of range\n" ;
        return 1 ;
    }

    // create an array of frequencies. frequencies[0] and frequencies[1] are unused
    // the vector initialises all the frequencies to zero
    std::vector<int> frequencies(number) ; // for factors up to number-1
    frequencies.push_back(1) ; // frequencies[number] == 1; a number is divisible by itself

    // for each factor of the number, starting with 2
    // other than the number itself, no other factor can be greater than half the number
    for( int factor = 2 ; factor <= (number/2) ; ++factor )
    {
        // set the number of times factor divides this number
        while( number%factor == 0 )
        {
            ++frequencies[factor] ;

            // this is ok, because if the number is divisible by factor,
            // we don't need to check for divisibility by factor*n
            // where n is greater than the factor
            // eg. if the number is divisible by 2, the frequency of factor 2 would be
            // higher than the frequency of the factors 2*3, 2*4 etc.
            number /= factor ;
        }

    }

    // determine the highest frequency, and also check if there is a tie
    int most_common_factor = 0 ;
    int max_frequency = 0 ;
    bool tie = false ;

    // need to use int( frequencies.size() ) here;
    // number does not contain the original value any more.
    for( int i = 2 ; i < int( frequencies.size() ) ; ++i )
    {
        if( frequencies[i] > max_frequency )
        {
            most_common_factor = i ;
            max_frequency = frequencies[i] ;
            tie = false ; // new high frequency, not seen earlier
        }
        else if( frequencies[i] == max_frequency ) tie = true ;
    }

    std::cout << "most common factor: " ;
    if(tie) std::cout << "NONE\n" ;
    else std::cout << most_common_factor << '\n' ;
}

http://coliru.stacked-crooked.com/a/59623a019e55d35f