Talk:Trial division

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Computing Start‑class Mid‑importance

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-importance on the project's importance scale.

Archives

Archive 1

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)[reply]

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.

A proper trial division should test that the square of f equals or exceeds n and stop trying any higher f values.