RuthAron Pairs

00001: /*
00002:  * Program: ruth-aaron.cc
00003:  * ----------------------
00004:  * Presents a short program which identifies
00005:  * and prints out the first 20 Ruth-Aaron pairs.
00006:  */
00007: 
00008: #include<iostream>
00009: #include<cmath>
00010: #include<vector>
00011: using namespace std;
00012: 
00013: 
00014: bool isPrime(int n)
00015: {
00016:     if (n == 1) return false;
00017:     if (n == 2) return true;
00018:     
00019:     for (int k = 2; k <= sqrt(double(n)) + 1; k++) {
00020:         if (n % k == 0)
00021:             return false;           
00022:     }
00023:     
00024:     return true;
00025: }
00026: 
00027: int factorSum(int num)
00028: {
00029:     int sum = 0;
00030:     if(isPrime(num))
00031:         sum = num;
00032:     else {while(num != 1){
00033:         for(int i =2; i <= num;i++) {
00034:           if(isPrime(i) && (num % i == 0)) {
00035:             sum += i;
00036:                 num /= i;
00037:             break;      
00038:           }
00039:         }
00040:     }
00041:     }
00042:     return sum;
00043: }
00044: 
00045: int main()
00046: {
00047:     int kNumRuthAaronPairsNeeded = 60;
00048:      // defines a constant variable so we know what 20 really is
00049:     
00050:     cout << "This program prints out the first " 
00051:         << kNumRuthAaronPairsNeeded
00052:          << " Ruth-Aaron pairs...." << endl;
00053:     cout << "And here they are:" << endl;
00054:     cout << "------------------" << endl;
00055:     
00056:     cout << endl; 
00057:     int j = 1;
00058:     while(kNumRuthAaronPairsNeeded != 0) {
00059:         
00060:       if(factorSum(j) == factorSum(j + 1)) {
00061:             cout << " " << 61 - kNumRuthAaronPairsNeeded <<"). "
00062:                 << j << " and " << j + 1 << endl; 
00063:                 kNumRuthAaronPairsNeeded--;
00064:         }
00065:         j = j + 1;
00066:     }
00067:     cout << endl;
00068:     
00069:     cout << "All done!" << endl;
00070:     return 0;
00071: }