Last updated at October 28, 2026 by Teachoo
Transcript
Think and Reflect (Page 41) Try to execute the algorithm to compute the divisors of 15, 135, and 775. How does the amount of work increase as the numbers grow? Our algorithm is Divisors of 15 We checks every integer from 1 to 15 Algorithm to find the divisors of ๐ Start with an empty list-of-divisors For each number ๐ in the sequence 1, 2, 3,โฆ,๐ If ๐ divides ๐, add ๐ to the end of list-of-divisors Report the completed list. Thus, divisors(15) = [1, 3, 5, 15] NUMBER J DIVISION TEST (15 + J) DOES J DIVIDE 15? ACTION LIST-OF-DIVISORS AFTER STEP 1 15=1x 15+0 v Yes (r = @) Add 1 to list [1] 2 15 =2x7+1 No (r = 1) Skip [1] 3 1=3x5+0 v Yes (r = 0) Add 3 to list [_. 31 4 15=4x3+3 No (r = 3) Skip [1, 3] 5 =5x3+0 Y Yes (r = @) Add 5 to list fi, 3, 5) 6 15=6x2+3 No (r = 3) Skip [1, 3, 5] 7 B=7x2+1 No (r = 1) Skip it, 3, 5] 8 5 =8x1+7 No (r = 7) Skip [1, 3, 5] 9 15 =9x1+6 No (r = 6) Skip [1, 3, 5] 10 15=10x1+5 No (r = 5) Skip [1, 3, 5] 11 15=11x1+4 No (r = 4) Skip [1, 3, 5] 12 15=12x1+3 No (r = 3) Skip [1, 3, 5] 13 15=13x1+2 No (r = 2) Skip i, 3, 51 14 15=14x1+1 No (r = 1) Skip [1, 3, 5] 15 15=15x1+0 v Yes (r = @) Add 15 to list [1 3, 5. 15] Divisors of 135 We checks every integer from 1 to 135 NUMBER J 10 11 12 13 14 15 16 17 18 19 20 DIVISION TEST (135 + J) 135 i * i135 +6 2x 67 +1 3 x 45 + 0 4x 33 +3 5 x 27 + 0 6 x 22 +3 7x19+2 8x 16+7 9x15 +6 10 x 13 +5 11 x 12 + 3 12 x 11+ 3 13 x 10 +5 14x9+9 15x9+0 16x 8+7 17 x 7 + 16 18 x 7+9 19x 7 +2 20 x 6 + 15 DOES J DIVIDE 135? Y Yes (r = 0) No (r = 3) No (r = 2) No (r = 7) No (r = 5) No (r = 9) No (r = 16) No (r = 15) ACTION Add 1 to list Skip Add 3 to list Add 5 to list Add 9 to list Add 15 to list LIST-OF-DIVISORS AFTER STEP [1] [1, 3] 5] 9] 15] 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 135 No (r = 9) (r = 3) (r = 20) (r = 15) (r = 10) (r = 5) Yes (r= (r = 23) (r = 19) (r = 11) (r = 7) (r = 33) (r = 30) (r = 27) (r = 24) (r = 21) (r = 18) (r = 12) ) Skip Add 27 to list [1, 15] 15, 27) 27] 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 62 63 64 135 ds 60 No (r v Yes 6) 3) 43) 41) 39) 37) 35) 33) 31) 29) 27) 25) 23) 21) 19) 17) 15) 13) 11) 9) 7) Skip Add 45 to list 15, i, 27] 275 27, 45] 65 66 67 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 135 68 86 No 5) 3) 1) 67) 66) 65) 64) 63) 62) 61) 60) 59) 58) 57) 56) 55) 54) 53) 52) 51) 50) 49) Skip 15, 27, 45] 87 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 135 87 x 1+ 48 88 x 1+ 47 89 x 1+ 46 90 x 1+ 45 91 x + 44 92 x 1+ 43 93 x 1+ 42 94x1+ 41 95 x 1+ 40 96 x 1+ 39 97 x 1+ 38 98 x 1+ 37 99 x 1 + 36 100 x 1+ 35 101 x 1+ 34 102 x 1 + 33 103 x 1 + 32 104 x 1+ 31 105 x 1+ 30 106 x 1+ 29 107 x 1+ 28 108 x 1+ 27 109 x 1+ 26 No 48) 47) 46) 45) 44) 43) 42) 41) 40) 39) 38) 37) 36) 35) 34) 33) 32) 31) 30) 29) 28) 27) 26) Skip [1, 15, 27, 45] 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 135 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 No (r 25) 24) 23) 22) 21) 20) 19) 18) 17) 16) 15) 14) 13) 12) 11) 10) 9) 8) 7) 6) 5) 4) Skip [1, 15, 27, 45] Thus, divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135] Divisors of 775 We checks every integer from 1 to 775 132 133 134 135 35) No (r = 3) No (r = 2) No (r = 1) v Yes (r = @) Skip Add 135 to list 15, alle}, 27, eu fe 45] 45, 135] 1) Input Number n Target Number Find all divisors of: n = 775 2 ) list-of-divisors = [] Step 1: Initialize Start with empty list: [ 1 (ready to collect) Vo 3} Sequence 1, 2, ..., 775 Step 2: Division Test 4 divisors(775) 6 divisors Test if j divides 775: n%*j= 0 Final List of Divisors: [1, 5, 25, 31, 155, 775] Total: 6 divisors found Thus, divisors(775) = [1, 5, 25, 31, 155, 775] How does the work increase? The algorithm performs n divisibility checks for input n. We observe that although 775 has fewer divisors than 135, it requires more checks. Thus, number of results and the amount of work are different quantities Number | Candidates checked | Divisors found 15 | 15 | 4 135 | 135 | 8 775 | 775 | 6