Как оптимизировать код для поиска дружных пар

Question

Пожалуйста, посмотрите код, который я использовал, чтобы найти, что я считаю, что все Дружные Пары (n, m), n http://tutoree7.pastebin.com/wKvMAWpT. Найденные пары: http://tutoree7.pastebin.com/dpEc0RbZ.

Я обнаружил, что каждый дополнительный миллион теперь занимает 24 минуты на моем ноутбуке. Я надеюсь, что есть существенные числа n, которые можно отфильтровать заранее. Это близко, но без сигары: странные n, которые не заканчиваются на «5». Пока существует только одна пара контрпримеров, но это слишком много: (34765731, 36939357). Это как фильтр отфильтровывает 40% всех n.

Я надеюсь на некоторые идеи, не обязательно код Python для их реализации.

Answer 1

#include<stdio.h>
#include<stdlib.h>
int sumOfFactors(int );

int main(){
    int x, y, start, end;
    printf("Enter start of the range:\n");
    scanf("%d", &start);
    printf("Enter end of the range:\n");
    scanf("%d", &end);

    for(x = start;x <= end;x++){
        for(y=end; y>= start;y--){
            if(x == sumOfFactors(y) && y == sumOfFactors(x) && x != y){
                printf("The numbers %d and %d are Amicable pair\n", x,y);
            }
        }
    }   
    return 0;
}

int sumOfFactors(int x){
    int sum = 1, i, j;
    for(j=2;j <= x/2;j++){
        if(x % j == 0)
            sum += j;
    }
    return sum;
}

Answer 2

def findSumOfFactors(n):
    sum = 1
    for i in range(2, int(n / 2) + 1):
        if n % i == 0:
            sum += i
    return sum

start = int(input())
end = int(input())

for i in range(start, end + 1):
    for j in range(end, start + 1, -1):
        if i is not j and findSumOfFactors(i) == j and findSumOfFactors(j) == i and j>1:
            print(i, j)

Answer 3

Вот хорошая статья, которая обобщает все методы оптимизации для поиска дружных пар

с образец кода C ++

Он находит все дружные числа до 10 ^ 9 менее чем за секунду.