C语言实现factor_count方法：返回整数正因数的个数

Alright, let's break down how to build this factor_count method step by step. First, let's make sure we're on the same page: given an integer, we need to return the total number of its positive divisors. For example, 32 has divisors 1, 2, 4, 8, 16, 32, so the method should spit out 6.

I'll walk through three approaches, from the simplest (but slow for big numbers) to the most efficient (great for large inputs).

1. Brute-force Approach (Simple but Not Ideal for Large Numbers) #

This is the most straightforward way—just loop through every number from 1 to the input integer, and count how many divide it evenly.

def factor_count(n):
    if n <= 0:
        return 0  # Non-positive numbers don't have positive divisors
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count

Pros & Cons #

• Pros: Super easy to write and understand—great for small numbers or when you're just testing logic.
• Cons: Terribly slow for large integers (like 10^9). You'd end up looping 1 billion times, which is not feasible.

2. Optimized Brute-force (Faster by Using Pairwise Divisors) #

Here's a smarter twist: divisors come in pairs. If d is a divisor of n, then n/d is also a divisor. That means we only need to loop up to the square root of n, not the whole number. We just have to be careful not to double-count when n is a perfect square (like 9, where 3 is paired with itself).

import math

def factor_count(n):
    if n <= 0:
        return 0
    count = 0
    sqrt_n = int(math.sqrt(n))
    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            # If it's a perfect square, count once
            if i == n // i:
                count += 1
            # Otherwise, count both pairs
            else:
                count += 2
    return count

How it works for 32: #

• The square root of 32 is ~5.65, so we loop from 1 to 5.
• 1 divides 32 → count +=2 (1 and 32)
• 2 divides 32 → count +=2 (2 and 16)
• 3 doesn't divide 32 → skip
• 4 divides 32 → count +=2 (4 and 8)
• 5 doesn't divide 32 → skip
• Total count is 6, which is correct.

Pros & Cons #

• Pros: Way faster than brute-force—for 10^9, we only loop ~30,000 times instead of 1 billion.
• Cons: Still not the most efficient for extremely large numbers (like 10^18), but it's a huge improvement.

3. Prime Factorization Method (Most Efficient for Large Numbers) #

This uses a number theory trick: if you factor n into its prime components (like 32 = 2^5), the number of positive divisors is the product of each prime's exponent plus one. For 32, that's 5 + 1 = 6—perfect match.

Here's how to implement it:

def factor_count(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1  # 1 has exactly one positive divisor (itself)
    
    count = 1
    # Handle even numbers first to optimize
    exponent = 0
    while n % 2 == 0:
        exponent += 1
        n = n // 2
    if exponent > 0:
        count *= (exponent + 1)
    
    # Now check odd numbers starting from 3
    i = 3
    while i * i <= n:
        exponent = 0
        while n % i == 0:
            exponent += 1
            n = n // i
        if exponent > 0:
            count *= (exponent + 1)
        i += 2  # Skip even numbers since we already handled 2
    
    # If remaining n is a prime number greater than 2
    if n > 2:
        count *= 2
    
    return count

How it works for 32: #

• We first count how many times 2 divides 32 (5 times). Multiply count by 5 + 1 → count becomes 6.
• Since after dividing out all 2s, n is 1, we're done. Return 6.

Pros & Cons #

• Pros: Blazing fast even for massive numbers. Prime factorization is much more efficient than looping through all possible divisors.
• Cons: A bit more code to write, but the efficiency gain is worth it for large inputs.

Test Cases to Verify #

Let's make sure the method works as expected:

• factor_count(32) → 6 ✔️
• factor_count(1) → 1 ✔️
• factor_count(9) → 3 (divisors: 1, 3, 9) ✔️
• factor_count(12) → 6 (divisors: 1, 2, 3, 4, 6, 12) ✔️

内容的提问来源于stack exchange，提问作者Vlad Ezikon