![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
|
|
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)
> 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)
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)
There are a bunch of well-meaning programmers who keep trying to improve the code listings, use fancier Python language features, add additional implementations in other programming languages, etc.
That's all missing the point. We're not trying to optimize, show off, showcase or compare programming languages, etc. We're just here to give the simplest and most accessible (mediocre) implementation we can, as a way of explaining the idea to novice readers. Anyone who wants to factorize numbers in their own program should not be copying code out of this article.
To reduce churn it might be better to just scrap the code listings entirely. We could write pseudocode or just a numbered list of prose sentences instead. – jacobolus (t) 06:18, 12 June 2024 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
|
|
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)
> 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)
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)
There are a bunch of well-meaning programmers who keep trying to improve the code listings, use fancier Python language features, add additional implementations in other programming languages, etc.
That's all missing the point. We're not trying to optimize, show off, showcase or compare programming languages, etc. We're just here to give the simplest and most accessible (mediocre) implementation we can, as a way of explaining the idea to novice readers. Anyone who wants to factorize numbers in their own program should not be copying code out of this article.
To reduce churn it might be better to just scrap the code listings entirely. We could write pseudocode or just a numbered list of prose sentences instead. – jacobolus (t) 06:18, 12 June 2024 (UTC)