Talk:Trial division
Mathematics Start‑class Mid‑priority | ||||||||||
|
Computing Start‑class Mid‑importance | ||||||||||
|
|
|
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)