Talk:Trial division

Python Example

The sample code is a pretty confusing example.

for p in prime_sieve(int(n**0.5)):
    if p*p > n: break

Especially because it calls a prime_sieve() function that's not explained and the if statement is redundant; prime_sieve(int(n**0.5)) already implies p*p can never be higher than n.

I'd propose replacing the imaginary prime_sieve() with some imaginary lookup of primes (or at least comment pointing it out), just because where the primes come from isn't the important part. Also, apart from just being slow, n**0.5 is meaningless for anyone unfamiliar with the syntax, using the math library is more human readable.

from math import sqrt

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    primes = prime_list(sqrt(n)) # call some other function to list all primes below the square root of n
    prime_factors = []
    for p in primes:
        while n % p == 0: # if n modulo p is 0 then p is a factor of n
            prime_factors.append(p)
            n //= p
        if n == 1: # stop if n is fully factorised
            break
    return prime_factors

This isn't very fast, but it's more human readable than the original, and the trivial cases aren't important for this example anyway. For extra simplicity, the n==1 break could be dropped too. MVHVTMV (talk) 09:12, 5 April 2017 (UTC)

Nope, doesn't work up to sqrt(n).

> In the worst case, trial division is a laborious algorithm. For a base-2 n digit number a, if it starts from two and works up to the square root of a.

Nope! If the input value n is prime, the code given will, increment the factor counter f all the way to n. At that point f divides n trivially, and n is reduced to 1, which terminates the loop.208.81.120.1 (talk) 22:43, 15 February 2018 (UTC)

Quite so. The better trial division methods don't go past sqrt(n), and hopefully, don't recalculate sqrt(n) at every iteration... NickyMcLean (talk) 08:37, 16 February 2018 (UTC)

If after dividing out factors up to sqrt(n), the result is not 1, that means the only prime factor is the number itself and it was prime. Wqwt (talk) 01:47, 27 December 2022 (UTC)

Time Complexity

Pseudo-polynomial time mentions trial division for primality testing. Is it the same for recursively factoring a number? Wqwt (talk) 01:48, 27 December 2022 (UTC)