使用Matlab求解Project Euler第12题：除数计数函数技术问询

Hey there! Let's break down your ND(n) function and make it more efficient for tackling Project Euler's 12th problem—since triangular numbers grow quickly, efficiency will be key once you start checking for numbers with hundreds of divisors.

First, Let's Talk About the Original Function's Limitations #

Your approach works for small values of n, but it has a big bottleneck: calling primes(n) generates every prime up to n itself. For large triangular numbers (like those with 500+ divisors), this is way more work than needed. You only ever need to check divisors up to the square root of n—any factor larger than that would pair with a smaller factor you've already found.

Additionally, while your loop logic works for most cases, relying on a pre-generated prime list can lead to unnecessary memory usage and slower execution as n scales.

A Faster Divisor-Counting Function #

Here's an optimized version that avoids generating all primes upfront and focuses on only the checks we need:

function [divisorCount] = countDivisors(n)
    % Handle the edge case of n=1 directly
    if n == 1
        divisorCount = 1;
        return;
    end

    divisorCount = 1;
    count = 0;

    % First check for factors of 2 (handles even numbers quickly)
    while rem(n, 2) == 0
        count = count + 1;
        n = n / 2;
    end
    divisorCount = divisorCount * (count + 1);

    % Now check odd numbers up to sqrt(n)
    i = 3;
    while i * i <= n
        count = 0;
        while rem(n, i) == 0
            count = count + 1;
            n = n / i;
        end
        divisorCount = divisorCount * (count + 1);
        i = i + 2; % Skip even numbers, since we already handled 2
    end

    % If the remaining n is a prime number greater than 2
    if n > 1
        divisorCount = divisorCount * 2;
    end
end

Key Optimizations:

• Separate handling of 2: Since even numbers are common, we check for factors of 2 first, then only iterate over odd numbers for the rest—cuts our loop iterations in half.
• Loop up to sqrt(n): No need to check every number up to n; once i*i exceeds n, any remaining n must be a prime number itself.
• No pre-generated primes: We don't waste time or memory generating primes we'll never use.

Even Better: Leverage Triangular Number Properties for Project Euler Problem 12 #

Triangular numbers follow the formula T_k = k*(k+1)/2. The best part? k and k+1 are consecutive integers, so they're coprime (they share no common factors other than 1). That means we can split the divisor count calculation into two smaller, faster problems:

• If k is even: Calculate divisors of k/2 and k+1, then multiply the two counts.
• If k is odd: Calculate divisors of k and (k+1)/2, then multiply the two counts.

This is way faster than calculating divisors for the full triangular number directly, since we're working with smaller numbers. Here's how to implement this:

function findHighlyDivisibleTriangularNumber(targetDivisors)
    k = 1;
    while true
        if mod(k, 2) == 0
            num1 = k / 2;
            num2 = k + 1;
        else
            num1 = k;
            num2 = (k + 1) / 2;
        end

        totalDivisors = countDivisors(num1) * countDivisors(num2);

        if totalDivisors > targetDivisors
            triangularNumber = k * (k + 1) / 2;
            fprintf('The first triangular number with over %d divisors is %d\n', targetDivisors, triangularNumber);
            return;
        end

        k = k + 1;
    end
end

Just call this function with your target (e.g., findHighlyDivisibleTriangularNumber(500) for the Project Euler problem) and it'll run much faster than your original approach.

内容的提问来源于stack exchange，提问作者Raphael Ferreira