vendredi 30 juillet 2021

Best way to find 'quite good' numbers up to 1 million?

I am working on an assignment involving 'quite good' numbers. The task describes them as:

"A "quite good" number is an integer whose "badness" – the size of the difference between the sum of its divisors and the number itself – is not greater than a specified value. For example, if the maximum badness is set at 3, there are 12 "quite good" numbers less than 100: 2, 3, 4, 6, 8, 10, 16, 18, 20, 28, 32, and 64; Your task is to write a C++ program, quitegood, that determines numbers of a specified maximum badness that are less than a specified value. The limiting value and maximum badness are specified as command-line arguments when the program is executed."

The task asks me to write a program that prints perfect numbers with a specified badness limit up to a million. So, the command line argument of quitegood 1000000 1 should print 2 4 6 8 16 28 32 64 128 256 496 512 1024 2048 4096 8128 8192 16384 32768 65536 131072 262144 524288.

I have gotten this to work with the following code

#include

using namespace std;

int main(int argc, char *argv[]) {

const int limit = argc > 1 ? atoi(argv[1]) : 1000000;
const int badness = argc > 2 ? atoi(argv[2]) : 10;

for(int number = 2; number < limit; number++) {
    int sum = 1;
    for (int factor = 2; factor < number; factor++){
        if (number % factor == 0) {
            sum += factor;
        }
    }

    if (number >= (sum - badness) && number <= (sum + badness)) {
        cout << number << " ";
    }
}

return 0;

}

The only issue is that this code is far too slow finding the 'quite good' numbers up to 1 million. Is there any way of optimising this?

Thank you

Aucun commentaire:

Enregistrer un commentaire