因子 素因子分解

Powered by:NEFU AB-IN

求因子种类

• i从1开始
• 要避免重复，如4*4

n = 24
vector<LL> v1;
for (int i = 1; i * i <= n; ++i)
{
    if (n % i == 0)
    {
        v1.push_back(i);
        if (n / i != i)
            v1.push_back(n / i);
    }
}
for (auto a : v1)
    cout << a << ' ';
cout << '\n';
//1 24 2 12 3 8 4 6

n = 24
lst = []
i = 1
while i * i <= n:
    if n % i == 0:
        lst.append(i)
        if n // i != i:
            lst.append(n // i)
    i += 1

素因子分解

• i从2开始
• 要加上最后的值

n = 24
vector<LL> v2;	
for (int i = 2; i * i <= n; ++i)
{
    while (n % i == 0)
    {
        n /= i;
        v2.push_back(i);
    }
}
if (n > 1)
    v2.push_back(n);
for (auto a : v2)
    cout << a << ' ';
cout << '\n';
//2 2 2 3