Поиск совершенных чисел на определённом интервале

#c #алгоритм #математика #оптимизация #простые_числа

Дано задание: В интервале [a,b] выведите все числа, такие, что сумма их делителей,
включая единицу, и не включая само число будет равна самому числу. Или -1, если таковых
чисел в интервале нет.

Необходимо оптимизировать алгоритм поиска, таким образом чтобы программа не зависала
при работе с большими числами. Попросту, чтобы после 80 000 не сообщала Time limit
exceeded Killed. Многие типы переменных и алгоритмы я ещё не использовал, поэтому информация
по данной тематике также важна. 

#include 

int main(){
    int a, b;
    scanf("%d %d", &a, &b);

    int counter = 0;
    for(int i = a; i <= b; i++) {
        int sum = 0;
        for(int j = 1; j < i; j++) {            
            if(i % j == 0) {
                sum += j;                
            }
        }
        if(sum == i) {
           printf("%d ", i);
           counter++;
        }        
    }

    if(counter == 0) {
        printf("-1");
    }

    return 0;
}

    

Ответы

Ответ 1

Вот, если очень хочется именно считать... пользуясь тем, что все известные на сегодня
совершенные числа четные, а еще Эйлер доказал их связь с простыми числами Мерсенна
- вот мы и подбираем простые Мерсенна, которые обеспечивают совершенные числа в нужном
диапазоне:


  Disclaimer: код as is, сваяно на коленке, просто показать, как должно работать.
Со всеми тонкостями типоразмеров и прочими просьба справляться самостоятельно и меня
не трогать :)


#include 
#include 
#include 

int isOddPrime(unsigned int u)
{
    for(unsigned int i = 3; i*i <= u; i+=2)
        if (u%i == 0) return 0;
    return 1;
}

unsigned int Perfect(unsigned int p)
{
    unsigned int Mersenne = (1u << p) - 1;
    if (!isOddPrime(Mersenne)) return 0;
    return Mersenne*(1u << (p-1));
}

int main()
{
    unsigned int a, b;
    scanf("%u %u",&a,&b);
    for(unsigned int p = 2;;++p)
    {
        unsigned long long s = (1ull << (2*p-1)) - (1ull << (p-1));
        if (s > b) break;
        if (s < a) continue;
        unsigned int res = Perfect(p);
        if (res) printf("%lu\n",res);
    }
}


Вывод к нужному виду (ну, там, -1 если чисел нет и т.п.) приведите сами...

P.S. А вообще, самая правильная программа на эту тему -

#include 
#include 

unsigned long long perfs[] =
{
    6,28,496,8128,33550336,8589869056,
    137438691328,2305843008139952128
};

int main()
{
    unsigned long long a, b;
    scanf("%llu %llu",&a,&b);
    int was = 0;
    for(int i = 0; i < 8; ++i)
    {
        if (perfs[i] >= a && perfs[i] <= b)
        {
            was = 1;
            printf("%llu\n",perfs[i]);
        }
    }
    if (!was) puts("-1");
}


:)

P.P.S. Всю необходимую информацию было очень легко получить, погулявшись, например,
в Википедию.


Ответ 2

Используй алгоритм, основанный на том же подходе, что и решето Эратосфена. Сделай
массив с суммой делителей, отличных от самого числа, а потом посчитай количество подходящих
чисел.



var a = Array(1000000+1).fill(0)

for (var q=1; q