Advertisement
makispaiktis

Filioi Arithmoi

Feb 27th, 2020 (edited)
303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <vector>
  5. #include <algorithm>
  6. #define N 10000
  7.  
  8. using namespace std;
  9.  
  10. // Auxiliary Functions
  11. vector <int> findDivisors(unsigned int n){
  12.     vector <int> divisors = vector <int> ();
  13.     divisors.push_back(1);
  14.     for(int i=2; i<=n/2; i++){
  15.         if(n % i == 0){
  16.             divisors.push_back(i);
  17.         }
  18.     }
  19.     return divisors;
  20. }
  21.  
  22. bool isPrime(unsigned int n){
  23.     // Prime numbers have only 2 divisors: 1 and n
  24.     // If I use the above function, the returned vector will contain only 1 divisor, specifically only the number 1
  25.     // Because I don't push back n as a divisor of number n
  26.     vector <int> divisors = findDivisors(n);
  27.     if(divisors.size() == 1){
  28.         return true;
  29.     }
  30.     else{
  31.         return false;
  32.     }
  33. }
  34.  
  35. int main()
  36. {
  37.     /*
  38.     // Check the function
  39.     for(int i=2; i<20; i++){
  40.         vector <int> v = vector <int> ();
  41.         v = findDivisors(i);
  42.         cout << i << " ----> ";
  43.         for(unsigned int j=0; j<v.size(); j++){
  44.             cout << v[j] << " ";
  45.         }
  46.         cout << endl;
  47.     }
  48.     */
  49.     vector <int> filioi = vector <int> ();
  50.     for(int i=2; i<=N; i++){
  51.         // First, I have to find the divisors of teach number i that I scan with the for-loop
  52.         vector <int> divisors1 = findDivisors(i);
  53.         int sum1 = 0;
  54.         for(unsigned int j=0; j<divisors1.size(); j++){
  55.             sum1 += divisors1[j];
  56.         }
  57.         // I will find the divisors of the sum1
  58.         // But first I have to check if it is prime
  59.         // Because if it is prime, I will have only 1 divisor (number 1)
  60.         if(isPrime(sum1)){
  61.             continue;
  62.         }
  63.         vector <int> divisors2 = findDivisors(sum1);
  64.         int sum2 = 0;
  65.         for(unsigned int j=0; j<divisors2.size(); j++){
  66.             sum2 += divisors2[j];
  67.         }
  68.         // Check if sum2 (sum of divisors of sum1) is equal to the number i
  69.         bool flag1 = (i == sum2);
  70.         bool flag2 = (i == sum1);
  71.         bool pairHasBeenInserted = false;
  72.         if(filioi.size() != 0){
  73.             for(unsigned int j=0; j<filioi.size(); j++){
  74.                 if(i == filioi[j]){
  75.                     pairHasBeenInserted = true;
  76.                     break;
  77.                 }
  78.             }
  79.         }
  80.         //cout << i << " ----> " << "flag1 = " << flag1 << ", flag2 = " << flag2 << endl;
  81.         // Now, I have to check if I have a perfect number
  82.         // In this case, i = sum2 but also i = sum1, because I have a perfect number and I don't want to
  83.         // include this case in my problem
  84.         if(flag1 == true && flag2 == false && pairHasBeenInserted == false){
  85.             filioi.push_back(i);
  86.             filioi.push_back(sum1);
  87.         }
  88.     }
  89.  
  90.     // The process for finding the pairs of filioi numbers has finished
  91.     cout << "Filioi Arithmoi: " << endl;
  92.     int counter = 0;
  93.     for(unsigned int i=0; i<filioi.size(); i+=2){
  94.         counter++;
  95.         cout << "Pair " << counter << ": " << filioi[i] << ", " << filioi[i+1] << endl;
  96.     }
  97.  
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement