Write a program that reads in a positive integer n and prints all the amicable pairs between 1 and n. Apart from the main function, there must be the following two functions in your program:
int summingFactors( int i ): return the sum of all proper factors of i.
void display( int n, int m ): if n 220, m 284, then prints
220 = 1 + 2 + 4 + 71 + 142
The screen dialog should appear as follows:
Enter a positive integer: 2000
Amicable pairs between 1 and 2000:
220 = 1 + 2 + 4 + 71 + 142
284 = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110
1184 = 1 + 2 + 5 + 10 + 11+ 22 + 55 + 110 + 121 + 242 + 605
1210 = 1 + 2 + 4 + 8 + 16 + 32 + 37 + 74 + 148 + 296 + 592
A pair of two positive integers is called an amicable (or friendly) pair if each equals to the sum of the proper divisors of the other (proper divisors means all the divisors excluding the number itself). Symbolically, a pair of two positive integers (m, n) is an amicable pair if s( m ) n and s( n ) m, where s( m ) and s( n ) are sum of proper divisors of m and n respectively. For example proper divisors of number 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110. The proper divisors of number 284 are 1, 2, 4, 71 and 142. Since
s(220) 1 2 4 5 10 11 20 22 44 55 110 284 and
s(284) 1 2 4 71 142 220,
(220, 284) is an amicable pair.
腦袋中想到的是迴圈，從1~2000 (每個數字A都跑因數和 (除了本身) ， 可是程式應該會執行的有點久 = =)
要怎麼要把每一個數字的因數和所得到的新數字B再求一次因數和(除了本身)再計算是否等於原先的A數字，這裡不好想...
1#include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 int integer;
8
9 cout <<"Enter a positive integer: ";
10 cin >> integer ;
11
12 cout <<"Amicable pairs between 1 and "<<integer<<":";
13 cout <<endl << endl ;
14
15 int num1=1 ;
16 int num2=1 ;
17
18 for( num1=1 ; num1<=integer ; num1++ )
19 {
20 int Sum2=0;
21 for ( int prime=1 ; prime <= num1 ; prime++ )
22 {
23 if( ( num1%prime )== 0 )
24 {
25 if( num1 != prime)
26 {
27 Sum2 = Sum2 + prime;
28 for( int i=2 ; i <= Sum2 ; i++ ) // sum2 is prime?
29 {
30 if ( (Sum2%i) == 0 )
31 {
32 num2 = Sum2 ;
33 }
34 }
35 }
36 }
37 }
38 int Sum1=0 ;
39
40 for ( int prime2=1 ; prime2 <= num2 ; prime2++)
41 {
42 if( ( num2%prime2)== 0 )
43 {
44 if( num2 != prime2 )
45 {
46 Sum1 = Sum1 + prime2 ;
47 }
48 }
49 }
50
51 if( num1 == Sum1 && num1 != num2)
52 {
53 if ( num1 < num2 )
54 {
55 cout << num1 <<" = 1" ;
56
57 int n = num2 ;
58 for ( int k=1 ; k <= n ; k++)
59 {
60 if( (n%k) == 0)
61 {
62 if ( n != k )
63 {
64 cout <<" + "<< k ;
65
66 }
67 }
68 }
69 cout <<endl<< num2 <<" = 1" ;
70
71 int m = num1 ;
72 for ( int s=2 ; s <= m ; s++)
73 {
74 if( (m%s) ==0)
75 {
76 if( m != s)
77 {
78 cout <<" + "<< s ;
79 }
80 }
81 }
82 cout << endl ;
83 }
84 }
85
86 }
87
88 return 0;
89 }
{
int sum;
int factor;
if (n == 1)
return 0;
sum = 1;
for (factor = 2; factor * factor < n; factor++)
if ((n % factor) == 0)
sum += factor + (n / factor);
if (factor * factor == n)
sum += factor;
return sum;
}
void Display(int n, int m)
{
printf("(%d,%d) is amicable pairs\n\n", n, m);
}
int main(int argCnt, char *argVal[])
{
int n, sn;
int m, sm;
for (m = 1; m <= 2000; m++)
{
sm = SummingFactors(m);
for (n = 1; n < m; n++)
{
sn = SummingFactors(n);
if ((n == sm) && (m == sn))
Display(n, m);
}
}
}
內文搜尋
從 APP 打開
X