Fast Number Factorization in Python
$begingroup$
Here's my implementation to factorize a positive integer:
def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2
return prime_factor_list
How can I improve this code in speed and make it pythonic?
python performance primes
$endgroup$
add a comment |
$begingroup$
Here's my implementation to factorize a positive integer:
def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2
return prime_factor_list
How can I improve this code in speed and make it pythonic?
python performance primes
$endgroup$
1
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54
add a comment |
$begingroup$
Here's my implementation to factorize a positive integer:
def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2
return prime_factor_list
How can I improve this code in speed and make it pythonic?
python performance primes
$endgroup$
Here's my implementation to factorize a positive integer:
def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2
return prime_factor_list
How can I improve this code in speed and make it pythonic?
python performance primes
python performance primes
edited Mar 4 '16 at 15:22
chepner
24315
24315
asked Mar 4 '16 at 6:26
user2305user2305
17825
17825
1
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54
add a comment |
1
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54
1
1
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
prime_factors()
The single greatest improvement to performance that you could make would be to remove the call to is_prime()
altogether. If all factors smaller than i
have been removed from n
already, then i
could not possibly be composite.
The next improvement you could make would be to turn prime_factors()
into a generator. The function would no longer need to resize and recopy prime_factor_list
whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.
Using three lines (i = 5
, while n != 1
, and i += 2
) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2)
header — is un-Pythonic. Such counting loops are usually better written using some kind of range()
, xrange()
, enumerate()
, or something from itertools
. Here, itertools.chain()
and itertools.count()
would be appropriate.
Without changing the spirit of your algorithm, I would write:
import itertools
def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i
is_prime()
As mentioned above, you don't need is_prime()
at all, if your only goal is to implement prime_factors()
.
However, if you wanted to implement is_prime()
anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i
multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.
Then, as with the other function, you should express the loop more Pythonically using range()
or xrange()
. Actually, you wouldn't need an explicit loop; you could use any()
instead.
So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:
def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))
$endgroup$
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller thani
have been removed fromn
already, theni
could not possibly be composite."i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, ifi
is composite, it will not divide the remainingn
, and I think that's what the OP was trying to skip. However, I do agree with removing the call tois_prime()
: trying to avoid aO(1)
operation with aO(log(n))
check is not exactly an optimization! :)
$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop ifn < i * i
and yieldn
as the largest prime factor.
$endgroup$
– Daniel
Mar 6 '16 at 15:37
add a comment |
$begingroup$
Your code is written fairly well, yet in is_prime
you forgot to check whether the input integer is 2; just add this:
if n == 2:
return True
Also, for some negative integers is_prime
returns True
. I suggest you add the following statement to prune them away:
if n <= 1:
return False
$endgroup$
add a comment |
$begingroup$
prime_factors
never calls is_prime
with a number that's divisible by 2 or 3. is_prime
could be faster if it used this knowledge. However, if is_prime
will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime
inside of prime_factors
.
Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen
, the final loop of the code would become:
while n != 1:
prime = next(gen)
while not n % prime:
prime_factor_list.append(prime)
n //= prime
$endgroup$
add a comment |
$begingroup$
Few additional thoughts to Fast Number Factorization in Python answer.
is_prime()
In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.
prime_factors()
There is one thing you miss in your code. Lets take prime number, let is be
$ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.
Now lets analyze your prime_factors
. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.
This trick can reduce time for such cases.
As the result, you can assume that you need to generate sieve up to square root of highest number.
$endgroup$
add a comment |
$begingroup$
def print_factors(x):enter code here
print("The factors of",x,"are:")enter code here
for i in range(1, num+1):enter code here
print()enter code here
print(i,"#--->",end=' ')enter code here
for j in range(1,i+1):enter code here
if i % j == 0:enter code here
print(j,end=', ')enter code here
num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
print_factors(num)enter code here
New contributor
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f121862%2ffast-number-factorization-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
prime_factors()
The single greatest improvement to performance that you could make would be to remove the call to is_prime()
altogether. If all factors smaller than i
have been removed from n
already, then i
could not possibly be composite.
The next improvement you could make would be to turn prime_factors()
into a generator. The function would no longer need to resize and recopy prime_factor_list
whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.
Using three lines (i = 5
, while n != 1
, and i += 2
) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2)
header — is un-Pythonic. Such counting loops are usually better written using some kind of range()
, xrange()
, enumerate()
, or something from itertools
. Here, itertools.chain()
and itertools.count()
would be appropriate.
Without changing the spirit of your algorithm, I would write:
import itertools
def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i
is_prime()
As mentioned above, you don't need is_prime()
at all, if your only goal is to implement prime_factors()
.
However, if you wanted to implement is_prime()
anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i
multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.
Then, as with the other function, you should express the loop more Pythonically using range()
or xrange()
. Actually, you wouldn't need an explicit loop; you could use any()
instead.
So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:
def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))
$endgroup$
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller thani
have been removed fromn
already, theni
could not possibly be composite."i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, ifi
is composite, it will not divide the remainingn
, and I think that's what the OP was trying to skip. However, I do agree with removing the call tois_prime()
: trying to avoid aO(1)
operation with aO(log(n))
check is not exactly an optimization! :)
$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop ifn < i * i
and yieldn
as the largest prime factor.
$endgroup$
– Daniel
Mar 6 '16 at 15:37
add a comment |
$begingroup$
prime_factors()
The single greatest improvement to performance that you could make would be to remove the call to is_prime()
altogether. If all factors smaller than i
have been removed from n
already, then i
could not possibly be composite.
The next improvement you could make would be to turn prime_factors()
into a generator. The function would no longer need to resize and recopy prime_factor_list
whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.
Using three lines (i = 5
, while n != 1
, and i += 2
) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2)
header — is un-Pythonic. Such counting loops are usually better written using some kind of range()
, xrange()
, enumerate()
, or something from itertools
. Here, itertools.chain()
and itertools.count()
would be appropriate.
Without changing the spirit of your algorithm, I would write:
import itertools
def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i
is_prime()
As mentioned above, you don't need is_prime()
at all, if your only goal is to implement prime_factors()
.
However, if you wanted to implement is_prime()
anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i
multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.
Then, as with the other function, you should express the loop more Pythonically using range()
or xrange()
. Actually, you wouldn't need an explicit loop; you could use any()
instead.
So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:
def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))
$endgroup$
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller thani
have been removed fromn
already, theni
could not possibly be composite."i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, ifi
is composite, it will not divide the remainingn
, and I think that's what the OP was trying to skip. However, I do agree with removing the call tois_prime()
: trying to avoid aO(1)
operation with aO(log(n))
check is not exactly an optimization! :)
$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop ifn < i * i
and yieldn
as the largest prime factor.
$endgroup$
– Daniel
Mar 6 '16 at 15:37
add a comment |
$begingroup$
prime_factors()
The single greatest improvement to performance that you could make would be to remove the call to is_prime()
altogether. If all factors smaller than i
have been removed from n
already, then i
could not possibly be composite.
The next improvement you could make would be to turn prime_factors()
into a generator. The function would no longer need to resize and recopy prime_factor_list
whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.
Using three lines (i = 5
, while n != 1
, and i += 2
) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2)
header — is un-Pythonic. Such counting loops are usually better written using some kind of range()
, xrange()
, enumerate()
, or something from itertools
. Here, itertools.chain()
and itertools.count()
would be appropriate.
Without changing the spirit of your algorithm, I would write:
import itertools
def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i
is_prime()
As mentioned above, you don't need is_prime()
at all, if your only goal is to implement prime_factors()
.
However, if you wanted to implement is_prime()
anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i
multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.
Then, as with the other function, you should express the loop more Pythonically using range()
or xrange()
. Actually, you wouldn't need an explicit loop; you could use any()
instead.
So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:
def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))
$endgroup$
prime_factors()
The single greatest improvement to performance that you could make would be to remove the call to is_prime()
altogether. If all factors smaller than i
have been removed from n
already, then i
could not possibly be composite.
The next improvement you could make would be to turn prime_factors()
into a generator. The function would no longer need to resize and recopy prime_factor_list
whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.
Using three lines (i = 5
, while n != 1
, and i += 2
) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2)
header — is un-Pythonic. Such counting loops are usually better written using some kind of range()
, xrange()
, enumerate()
, or something from itertools
. Here, itertools.chain()
and itertools.count()
would be appropriate.
Without changing the spirit of your algorithm, I would write:
import itertools
def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i
is_prime()
As mentioned above, you don't need is_prime()
at all, if your only goal is to implement prime_factors()
.
However, if you wanted to implement is_prime()
anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i
multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.
Then, as with the other function, you should express the loop more Pythonically using range()
or xrange()
. Actually, you wouldn't need an explicit loop; you could use any()
instead.
So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:
def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))
edited Mar 4 '16 at 9:13
answered Mar 4 '16 at 9:00
200_success200_success
130k16153417
130k16153417
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller thani
have been removed fromn
already, theni
could not possibly be composite."i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, ifi
is composite, it will not divide the remainingn
, and I think that's what the OP was trying to skip. However, I do agree with removing the call tois_prime()
: trying to avoid aO(1)
operation with aO(log(n))
check is not exactly an optimization! :)
$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop ifn < i * i
and yieldn
as the largest prime factor.
$endgroup$
– Daniel
Mar 6 '16 at 15:37
add a comment |
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller thani
have been removed fromn
already, theni
could not possibly be composite."i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, ifi
is composite, it will not divide the remainingn
, and I think that's what the OP was trying to skip. However, I do agree with removing the call tois_prime()
: trying to avoid aO(1)
operation with aO(log(n))
check is not exactly an optimization! :)
$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop ifn < i * i
and yieldn
as the largest prime factor.
$endgroup$
– Daniel
Mar 6 '16 at 15:37
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
using is_prime was really dumb. Good Observation.
$endgroup$
– user2305
Mar 4 '16 at 10:51
$begingroup$
@200_success @user2305 "If all factors smaller than
i
have been removed from n
already, then i
could not possibly be composite." i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i
is composite, it will not divide the remaining n
, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime()
: trying to avoid a O(1)
operation with a O(log(n))
check is not exactly an optimization! :)$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success @user2305 "If all factors smaller than
i
have been removed from n
already, then i
could not possibly be composite." i
can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i
is composite, it will not divide the remaining n
, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime()
: trying to avoid a O(1)
operation with a O(log(n))
check is not exactly an optimization! :)$endgroup$
– OxTaz
Mar 4 '16 at 17:16
$begingroup$
@200_success: you can break the loop if
n < i * i
and yield n
as the largest prime factor.$endgroup$
– Daniel
Mar 6 '16 at 15:37
$begingroup$
@200_success: you can break the loop if
n < i * i
and yield n
as the largest prime factor.$endgroup$
– Daniel
Mar 6 '16 at 15:37
add a comment |
$begingroup$
Your code is written fairly well, yet in is_prime
you forgot to check whether the input integer is 2; just add this:
if n == 2:
return True
Also, for some negative integers is_prime
returns True
. I suggest you add the following statement to prune them away:
if n <= 1:
return False
$endgroup$
add a comment |
$begingroup$
Your code is written fairly well, yet in is_prime
you forgot to check whether the input integer is 2; just add this:
if n == 2:
return True
Also, for some negative integers is_prime
returns True
. I suggest you add the following statement to prune them away:
if n <= 1:
return False
$endgroup$
add a comment |
$begingroup$
Your code is written fairly well, yet in is_prime
you forgot to check whether the input integer is 2; just add this:
if n == 2:
return True
Also, for some negative integers is_prime
returns True
. I suggest you add the following statement to prune them away:
if n <= 1:
return False
$endgroup$
Your code is written fairly well, yet in is_prime
you forgot to check whether the input integer is 2; just add this:
if n == 2:
return True
Also, for some negative integers is_prime
returns True
. I suggest you add the following statement to prune them away:
if n <= 1:
return False
edited Mar 4 '16 at 8:46
answered Mar 4 '16 at 6:44
coderoddecoderodde
15.9k638127
15.9k638127
add a comment |
add a comment |
$begingroup$
prime_factors
never calls is_prime
with a number that's divisible by 2 or 3. is_prime
could be faster if it used this knowledge. However, if is_prime
will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime
inside of prime_factors
.
Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen
, the final loop of the code would become:
while n != 1:
prime = next(gen)
while not n % prime:
prime_factor_list.append(prime)
n //= prime
$endgroup$
add a comment |
$begingroup$
prime_factors
never calls is_prime
with a number that's divisible by 2 or 3. is_prime
could be faster if it used this knowledge. However, if is_prime
will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime
inside of prime_factors
.
Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen
, the final loop of the code would become:
while n != 1:
prime = next(gen)
while not n % prime:
prime_factor_list.append(prime)
n //= prime
$endgroup$
add a comment |
$begingroup$
prime_factors
never calls is_prime
with a number that's divisible by 2 or 3. is_prime
could be faster if it used this knowledge. However, if is_prime
will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime
inside of prime_factors
.
Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen
, the final loop of the code would become:
while n != 1:
prime = next(gen)
while not n % prime:
prime_factor_list.append(prime)
n //= prime
$endgroup$
prime_factors
never calls is_prime
with a number that's divisible by 2 or 3. is_prime
could be faster if it used this knowledge. However, if is_prime
will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime
inside of prime_factors
.
Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen
, the final loop of the code would become:
while n != 1:
prime = next(gen)
while not n % prime:
prime_factor_list.append(prime)
n //= prime
answered Mar 4 '16 at 7:40
janosjanos
98.1k12125350
98.1k12125350
add a comment |
add a comment |
$begingroup$
Few additional thoughts to Fast Number Factorization in Python answer.
is_prime()
In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.
prime_factors()
There is one thing you miss in your code. Lets take prime number, let is be
$ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.
Now lets analyze your prime_factors
. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.
This trick can reduce time for such cases.
As the result, you can assume that you need to generate sieve up to square root of highest number.
$endgroup$
add a comment |
$begingroup$
Few additional thoughts to Fast Number Factorization in Python answer.
is_prime()
In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.
prime_factors()
There is one thing you miss in your code. Lets take prime number, let is be
$ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.
Now lets analyze your prime_factors
. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.
This trick can reduce time for such cases.
As the result, you can assume that you need to generate sieve up to square root of highest number.
$endgroup$
add a comment |
$begingroup$
Few additional thoughts to Fast Number Factorization in Python answer.
is_prime()
In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.
prime_factors()
There is one thing you miss in your code. Lets take prime number, let is be
$ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.
Now lets analyze your prime_factors
. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.
This trick can reduce time for such cases.
As the result, you can assume that you need to generate sieve up to square root of highest number.
$endgroup$
Few additional thoughts to Fast Number Factorization in Python answer.
is_prime()
In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.
prime_factors()
There is one thing you miss in your code. Lets take prime number, let is be
$ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.
Now lets analyze your prime_factors
. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.
This trick can reduce time for such cases.
As the result, you can assume that you need to generate sieve up to square root of highest number.
edited Apr 13 '17 at 12:40
Community♦
1
1
answered Mar 4 '16 at 9:57
outoftimeoutoftime
1,392517
1,392517
add a comment |
add a comment |
$begingroup$
def print_factors(x):enter code here
print("The factors of",x,"are:")enter code here
for i in range(1, num+1):enter code here
print()enter code here
print(i,"#--->",end=' ')enter code here
for j in range(1,i+1):enter code here
if i % j == 0:enter code here
print(j,end=', ')enter code here
num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
print_factors(num)enter code here
New contributor
$endgroup$
add a comment |
$begingroup$
def print_factors(x):enter code here
print("The factors of",x,"are:")enter code here
for i in range(1, num+1):enter code here
print()enter code here
print(i,"#--->",end=' ')enter code here
for j in range(1,i+1):enter code here
if i % j == 0:enter code here
print(j,end=', ')enter code here
num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
print_factors(num)enter code here
New contributor
$endgroup$
add a comment |
$begingroup$
def print_factors(x):enter code here
print("The factors of",x,"are:")enter code here
for i in range(1, num+1):enter code here
print()enter code here
print(i,"#--->",end=' ')enter code here
for j in range(1,i+1):enter code here
if i % j == 0:enter code here
print(j,end=', ')enter code here
num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
print_factors(num)enter code here
New contributor
$endgroup$
def print_factors(x):enter code here
print("The factors of",x,"are:")enter code here
for i in range(1, num+1):enter code here
print()enter code here
print(i,"#--->",end=' ')enter code here
for j in range(1,i+1):enter code here
if i % j == 0:enter code here
print(j,end=', ')enter code here
num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
print_factors(num)enter code here
New contributor
New contributor
answered 22 mins ago
VasanthVasanth
1
1
New contributor
New contributor
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f121862%2ffast-number-factorization-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54