Comment optimiser le code pour trouver des paires amiables

Question

Veuillez voir le code que j'ai utilisé pour trouver ce que je crois être toutes les paires amiables (n, m), n < m, 2 < = n < = 65 millions. Mon code: http://tutoree7.pastebin.com/wKvMAWpT. Les paires trouvées: http://tutoree7.pastebin.com/dpEc0RbZ.

Je constate que chaque million supplémentaire prend maintenant 24 minutes sur mon ordinateur portable. J'espère qu'il y aura un nombre important de n qui peuvent être filtrés à l'avance. Cela se rapproche, mais pas de cigare: impair n qui ne se termine pas en «5». Il n'y a qu'une seule paire de contre-exemples jusqu'à maintenant, mais c'est une de trop: (34765731, 36939357). Cela en tant que filtre permettrait de filtrer 40% de tous n.

J'espère avoir quelques idées, pas nécessairement le code Python pour les implémenter.

Answer 1

Voici un bel article qui résume toutes les techniques d'optimisation pour finding amicable pairs

avec sample C++ code

Il trouve tous les nombres amiables jusqu'à 10^9 en moins d'une seconde.

Answer 2

#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 3

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)