Φιλοι Αριθμοι αλγόριθμος

[@_zerocool]

Σας παραθέτω μια άσκηση, μπορεί κάποιος να μου τη λύσει με ένα αναδρομικό αλγόριθμο?

 

 

Εστω χ, ψ φυσικοι αριθμοί και χ1 χ2 ... χν οι διαιρέτες του χ και ψ1 ψ2 ... ψν οι διαιρέτες του ψ.

 

Εαν χ1+χ2 .... +χν = ψ και ψ1+ψ2 .... +ψν = χ τοτε (χ,ψ) Φιλιοι αριθμοι

 

1 -> Ν , Ν > 1.000.000

 

[code]

 

Έχετε καμία βοηθεια?

[Sta]

Τι πρέπει να κάνει ο αλγόριθμος; Να διαπιστώνει, δοθέντων δύο αριθμών, αν είναι φίλιοι;

[bird]

Αυτό που δεν κατάλαβα είναι το: 1 -> Ν , Ν > 1.000.000

Τι ακριβώς εννοείς?

 

@Sta: Έτσι όπως το λέει μάλλον αυτό που λές θα πρέπει να κάνει ο αλγόριθμος...

[bird]

Μία γρήγορη προσέγγιση...

Το γράφω απευθείας και δεν ξέρω αν έχει λάθη... (δεν έχω compiler εδώ που είμαι...)

 

 

>
int friends( int x, int y)
{
  // Ορισμός μεταβλητών
  int i;
  int sumx, sumy;

  sumx=sumy=0;
  
  // Βρίσκεις τους διαιρέτες του χ και τους προσθέτεις
  for (  i = 1; i < x+1; i++ )
      if ( !(x % i) ) sumx += i;

  // Αν το άθροισμα δέν κάνει y, οι αριθμοί δεν ειναι φίλοι
  if ( y != sumx ) return(0);

  // Βρίσκεις τους διαιρέτες του y και τους προσθέτεις
  for (  i = 1; i < y+1; i++ )
      if ( !(y % i) ) sumy += i;

  // Αν το άθροισμα δέν κάνει χ, οι αριθμοί δεν ειναι φίλοι
  if ( y != sumy ) return(0);

  // Αλλοιώς οι αριθμοί είναι φίλοι...
  return(1);
 
}

 

Ελπίζω να βοήθησα...

[Sta]

Μικρή διόρθωση στον προηγούμενο αλγόριθμο: στους διαιρέτες του x δεν πρέπει να συμπεριλαμβάνεται ο ίδιος ο x. Οπότε, οι βρόχοι είναι μέχρι x και όχι x+1. Προτείνω κι εγώ μία λύση για παραγωγή φίλιων αριθμών, είναι πολύ αργή και όχι εξαντλητικά ελεγμένη:

 

>
#include <stdio.h>
#include <limits.h>

unsigned long long restricted_divisor(unsigned long long i)
{
        unsigned long long k;
        unsigned long long sum=0;
        for (k=1;k<i;k++)
        {
            if (i%k==0)
               sum+=k;
        }
        return sum;
}

int main(void)
{
   unsigned long long i,previous=0;
   
   
   for (i=1;i<=ULONG_MAX;i++)
   {
       if (previous==i) continue;
       unsigned long long k = restricted_divisor(i);
       if (k!=i && restricted_divisor(k)==i) {
                previous=k;
                printf("Amicable pair: (%lld,%lld)\n",i,k);
       }
   }
   return 0;
}

[@_zerocool]

eyxaristw poly paidia