c++ 需要查找第二大因子数,但不使用数组

dauxcl2d  于 2023-03-05  发布在  其他
关注(0)|答案(2)|浏览(91)

我在求因子数,除了1以外,我不认为整数本身是因子:

int factor (int num) {
    int result;
    for (int i = 1; i < num/2; i++) {   
        if (num % i == 0) {
            result = i;
        }
    }
    return result;
}
rdlzhqv9

rdlzhqv91#

你的代码已经基本完成了。你需要在循环之后得到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

vs3odd8k

vs3odd8k2#

当你谈到因子时,你可能只指素因子。
第二大可以很容易地存储,而不需要数组,只需使用两个变量,cur(当前)和prev(先前),两者都保存一个因子。
你需要做除法本身(不仅仅是模),因为如果你只是检查num % i,那么你可能会发现非素因子,但你只对素数感兴趣,这就是为什么你需要除法num /= i;,这将确保只有素因子留下。
此外,通过只计算数字平方根的因子也可以很容易地提高代码的速度。众所周知,如果我们搜索小于sqrt(num)的因子,那么剩下的因子将保证是单素数。
如果你只除以奇数因子,那么加速两倍是很容易的,但是你需要从因子中删除素数2。我做这个优化并不是为了简化代码,但是如果你对它感兴趣,请在评论中告诉我。
请参见代码后面的输出值示例。
Try it online!

#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,

相关问题