Алгоритм определения правильных делителей

Question

Я заинтересован в нахождении чисел, которые обладают свойством иметь сумму их собственных делителей, равную числу. Первый пример - 6, где правильные делители: 1 + 2 + 3 = 6.

Я написал следующий код на R, но чувствую, что он довольно неэффективен и может быть значительно улучшен.

propDivisor <- function(
    max
)
{
    n<-{}
    for(j in 2:max){
        m<-{}
        for(i in 1:(j/2+1)){
            if(j%%i==0){m<-c(m,i)}
        }   
        if(sum(m)==j){n<-c(n,j)}
    }
return(cat("The proper divisors between 1 and", max, "are", n, ".", sep=" ")    )
}

У кого-нибудь есть предложения по улучшению следующего кода? Я чувствую, что одна из функций применения должна использоваться здесь. Может быть, это будет достойное упражнение для игры в гольф на будущее?

И, как я знаю, здесь это встречается довольно часто, это НЕ домашняя проблема, просто что-то, что коллега изобразил интересным претендентом на программирование сегодня.

UPDATE:

Спасибо всем за ваши комментарии и мысли о местах, чтобы искать дополнительную информацию. Вот еще одно решение, которое использует sapply:

D <- function(n) sum((1:(n-1))[n%%1:(n-1)==0])==n
(2:9000)[sapply(2:9000,D)]

Answer 1

То, что вы ищете, называется совершенными числами (сумма правильных делителей равна самому числу).

Если вы хотите улучшить сам подход, см. Здесь .

Чтобы найти правильные делители, вы должны улучшить, как в начале:

• Ваш цикл может остановиться на sqrt (max)
• И каждый раз, когда вы найдетеделитель i, max / i тоже является делителем, если только max / i == i не будет учитываться.

Answer 2

Числа вида 2 ^ (n-1) * (2 ^ n -1) являются идеальными числами, если 2 ^ n - 1 является простым

Answer 3

#include<stdio.h>
#include<math.h>
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                long long int n,i,sum= -n;
                scanf("%lld",&n);
                for(i=1;i<=sqrt(n);i++)
                {
                        if(n%i==0)
                        sum = sum + i + n/i;
                }
                printf("%lld\n",sum);
        }
        return 0;
}

~