我在求因子数,除了1以外,我不认为整数本身是因子:
int factor (int num) { int result; for (int i = 1; i < num/2; i++) { if (num % i == 0) { result = i; } } return result; }
rdlzhqv91#
你的代码已经基本完成了。你需要在循环之后得到return result。
return result
int factor (int num) { int result = 0; for (int i = 1; i < num/2; i++) { if (num % i == 0) { result = i; } } return result; }
因为你有i < num/2,所以你永远不会考虑最大的因素,它跟随第二大的因素,这就是你的返回值。live test onlinegdb
i < num/2
vs3odd8k2#
当你谈到因子时,你可能只指素因子。第二大可以很容易地存储,而不需要数组,只需使用两个变量,cur(当前)和prev(先前),两者都保存一个因子。你需要做除法本身(不仅仅是模),因为如果你只是检查num % i,那么你可能会发现非素因子,但你只对素数感兴趣,这就是为什么你需要除法num /= i;,这将确保只有素因子留下。此外,通过只计算数字平方根的因子也可以很容易地提高代码的速度。众所周知,如果我们搜索小于sqrt(num)的因子,那么剩下的因子将保证是单素数。如果你只除以奇数因子,那么加速两倍是很容易的,但是你需要从因子中删除素数2。我做这个优化并不是为了简化代码,但是如果你对它感兴趣,请在评论中告诉我。请参见代码后面的输出值示例。Try it online!
cur
prev
num % i
num /= i;
#include <iostream> #include <iomanip> int factor(int num) { int prev = 1, cur = 1; for (int i = 2; i * i <= num; ++i) while (num % i == 0) { prev = cur; cur = i; num /= i; } return num <= 1 ? prev : cur; } int main() { for (size_t i = 0; i < 200; ++i) std::cout << std::setw(3) << i << " -> " << std::setw(2) << factor(i) << ", " << ((i + 1) % 7 == 0 ? "\n" : ""); }
输出:
0 -> 1, 1 -> 1, 2 -> 1, 3 -> 1, 4 -> 2, 5 -> 1, 6 -> 2, 7 -> 1, 8 -> 2, 9 -> 3, 10 -> 2, 11 -> 1, 12 -> 2, 13 -> 1, 14 -> 2, 15 -> 3, 16 -> 2, 17 -> 1, 18 -> 3, 19 -> 1, 20 -> 2, 21 -> 3, 22 -> 2, 23 -> 1, 24 -> 2, 25 -> 5, 26 -> 2, 27 -> 3, 28 -> 2, 29 -> 1, 30 -> 3, 31 -> 1, 32 -> 2, 33 -> 3, 34 -> 2, 35 -> 5, 36 -> 3, 37 -> 1, 38 -> 2, 39 -> 3, 40 -> 2, 41 -> 1, 42 -> 3, 43 -> 1, 44 -> 2, 45 -> 3, 46 -> 2, 47 -> 1, 48 -> 2, 49 -> 7, 50 -> 5, 51 -> 3, 52 -> 2, 53 -> 1, 54 -> 3, 55 -> 5, 56 -> 2, 57 -> 3, 58 -> 2, 59 -> 1, 60 -> 3, 61 -> 1, 62 -> 2, 63 -> 3, 64 -> 2, 65 -> 5, 66 -> 3, 67 -> 1, 68 -> 2, 69 -> 3, 70 -> 5, 71 -> 1, 72 -> 3, 73 -> 1, 74 -> 2, 75 -> 5, 76 -> 2, 77 -> 7, 78 -> 3, 79 -> 1, 80 -> 2, 81 -> 3, 82 -> 2, 83 -> 1, 84 -> 3, 85 -> 5, 86 -> 2, 87 -> 3, 88 -> 2, 89 -> 1, 90 -> 3, 91 -> 7, 92 -> 2, 93 -> 3, 94 -> 2, 95 -> 5, 96 -> 2, 97 -> 1, 98 -> 7, 99 -> 3, 100 -> 5, 101 -> 1, 102 -> 3, 103 -> 1, 104 -> 2, 105 -> 5, 106 -> 2, 107 -> 1, 108 -> 3, 109 -> 1, 110 -> 5, 111 -> 3, 112 -> 2, 113 -> 1, 114 -> 3, 115 -> 5, 116 -> 2, 117 -> 3, 118 -> 2, 119 -> 7, 120 -> 3, 121 -> 11, 122 -> 2, 123 -> 3, 124 -> 2, 125 -> 5, 126 -> 3, 127 -> 1, 128 -> 2, 129 -> 3, 130 -> 5, 131 -> 1, 132 -> 3, 133 -> 7, 134 -> 2, 135 -> 3, 136 -> 2, 137 -> 1, 138 -> 3, 139 -> 1, 140 -> 5, 141 -> 3, 142 -> 2, 143 -> 11, 144 -> 3, 145 -> 5, 146 -> 2, 147 -> 7, 148 -> 2, 149 -> 1, 150 -> 5, 151 -> 1, 152 -> 2, 153 -> 3, 154 -> 7, 155 -> 5, 156 -> 3, 157 -> 1, 158 -> 2, 159 -> 3, 160 -> 2, 161 -> 7, 162 -> 3, 163 -> 1, 164 -> 2, 165 -> 5, 166 -> 2, 167 -> 1, 168 -> 3, 169 -> 13, 170 -> 5, 171 -> 3, 172 -> 2, 173 -> 1, 174 -> 3, 175 -> 5, 176 -> 2, 177 -> 3, 178 -> 2, 179 -> 1, 180 -> 3, 181 -> 1, 182 -> 7, 183 -> 3, 184 -> 2, 185 -> 5, 186 -> 3, 187 -> 11, 188 -> 2, 189 -> 3, 190 -> 5, 191 -> 1, 192 -> 2, 193 -> 1, 194 -> 2, 195 -> 5, 196 -> 7, 197 -> 1, 198 -> 3, 199 -> 1,
2条答案
按热度按时间rdlzhqv91#
你的代码已经基本完成了。你需要在循环之后得到
return result
。因为你有
i < num/2
,所以你永远不会考虑最大的因素,它跟随第二大的因素,这就是你的返回值。live test onlinegdb
vs3odd8k2#
当你谈到因子时,你可能只指素因子。
第二大可以很容易地存储,而不需要数组,只需使用两个变量,
cur
(当前)和prev
(先前),两者都保存一个因子。你需要做除法本身(不仅仅是模),因为如果你只是检查
num % i
,那么你可能会发现非素因子,但你只对素数感兴趣,这就是为什么你需要除法num /= i;
,这将确保只有素因子留下。此外,通过只计算数字平方根的因子也可以很容易地提高代码的速度。众所周知,如果我们搜索小于sqrt(num)的因子,那么剩下的因子将保证是单素数。
如果你只除以奇数因子,那么加速两倍是很容易的,但是你需要从因子中删除素数2。我做这个优化并不是为了简化代码,但是如果你对它感兴趣,请在评论中告诉我。
请参见代码后面的输出值示例。
Try it online!
输出: