Fast Factorisation (Python Implementation)
$begingroup$
An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is $O(n^{1/2})$, the best case would be $O(log(n))$, and I don't know how to calculate average case or amortised worst case. I am aware that this is not strictly optimal, but I think it is easier to understand and implement, than say Pollard's rho algorithm for prime factorisation (I suspect it works better if the number is composite with many prime factors as well). Suggestions for improvements are welcome.
FastFactorise.py
def fact(n):
"""
* Function to factorise a given number given a list of prime numbers up to the square root of the number.
* Parameters:
* `n`: The number to be factorised.
* Return:
* `res`: A dict mapping each factor to its power in the prime factorisation of the number.
* Algorithm:
* Step 1: Initialise `res` to an empty dictionary.
* Step 2: If `n` > 1.
* Step 3: Iterate through the prime number list.
* Step 4: If ever the current prime number is > the floor of the square root of `n` + 1 exit the loop.
* Step 5: If the current prime number is a factor of `n`.
* Step 6: Assign 0 to `e`.
* Step 7: While the current prime number is a factor of `n`.
* Step 8: Increment `e`.
* Step 9: Divide `n` by the current prime number.
* [End of Step 7 while loop.]
* Step 10: Map the current prime number to `e` in the result dictionary.
* [End of step 5 if block.]
* Step 11: If `n` is not 1 (after the repeated dividings) map `n` to 1 in the result dictionary.
* Step 12: Return the result dictionary.
* [Exit the function.]
"""
res = {}
if n > 1:
for p in primes:
if p > int(sqrt(n)) + 1: break
if n%p == 0:
e = 0
while n%p == 0:
e += 1
n //= p
res[p] = e
if n != 1: res[n] = 1
return res
python performance beginner algorithm primes
edited 4 hours ago
Jamal♦
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
$endgroup$
add a comment |
$begingroup$
An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is $O(n^{1/2})$, the best case would be $O(log(n))$, and I don't know how to calculate average case or amortised worst case. I am aware that this is not strictly optimal, but I think it is easier to understand and implement, than say Pollard's rho algorithm for prime factorisation (I suspect it works better if the number is composite with many prime factors as well). Suggestions for improvements are welcome.
FastFactorise.py
def fact(n):
"""
* Function to factorise a given number given a list of prime numbers up to the square root of the number.
* Parameters:
* `n`: The number to be factorised.
* Return:
* `res`: A dict mapping each factor to its power in the prime factorisation of the number.
* Algorithm:
* Step 1: Initialise `res` to an empty dictionary.
* Step 2: If `n` > 1.
* Step 3: Iterate through the prime number list.
* Step 4: If ever the current prime number is > the floor of the square root of `n` + 1 exit the loop.
* Step 5: If the current prime number is a factor of `n`.
* Step 6: Assign 0 to `e`.
* Step 7: While the current prime number is a factor of `n`.
* Step 8: Increment `e`.
* Step 9: Divide `n` by the current prime number.
* [End of Step 7 while loop.]
* Step 10: Map the current prime number to `e` in the result dictionary.
* [End of step 5 if block.]
* Step 11: If `n` is not 1 (after the repeated dividings) map `n` to 1 in the result dictionary.
* Step 12: Return the result dictionary.
* [Exit the function.]
"""
res = {}
if n > 1:
for p in primes:
if p > int(sqrt(n)) + 1: break
if n%p == 0:
e = 0
while n%p == 0:
e += 1
n //= p
res[p] = e
if n != 1: res[n] = 1
return res
python performance beginner algorithm primes
edited 4 hours ago
Jamal♦
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
$endgroup$
add a comment |
$begingroup$
An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is $O(n^{1/2})$, the best case would be $O(log(n))$, and I don't know how to calculate average case or amortised worst case. I am aware that this is not strictly optimal, but I think it is easier to understand and implement, than say Pollard's rho algorithm for prime factorisation (I suspect it works better if the number is composite with many prime factors as well). Suggestions for improvements are welcome.
FastFactorise.py
def fact(n):
"""
* Function to factorise a given number given a list of prime numbers up to the square root of the number.
* Parameters:
* `n`: The number to be factorised.
* Return:
* `res`: A dict mapping each factor to its power in the prime factorisation of the number.
* Algorithm:
* Step 1: Initialise `res` to an empty dictionary.
* Step 2: If `n` > 1.
* Step 3: Iterate through the prime number list.
* Step 4: If ever the current prime number is > the floor of the square root of `n` + 1 exit the loop.
* Step 5: If the current prime number is a factor of `n`.
* Step 6: Assign 0 to `e`.
* Step 7: While the current prime number is a factor of `n`.
* Step 8: Increment `e`.
* Step 9: Divide `n` by the current prime number.
* [End of Step 7 while loop.]
* Step 10: Map the current prime number to `e` in the result dictionary.
* [End of step 5 if block.]
* Step 11: If `n` is not 1 (after the repeated dividings) map `n` to 1 in the result dictionary.
* Step 12: Return the result dictionary.
* [Exit the function.]
"""
res = {}
if n > 1:
for p in primes:
if p > int(sqrt(n)) + 1: break
if n%p == 0:
e = 0
while n%p == 0:
e += 1
n //= p
res[p] = e
if n != 1: res[n] = 1
return res
python performance beginner algorithm primes
edited 4 hours ago
Jamal♦
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
$endgroup$
An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is $O(n^{1/2})$, the best case would be $O(log(n))$, and I don't know how to calculate average case or amortised worst case. I am aware that this is not strictly optimal, but I think it is easier to understand and implement, than say Pollard's rho algorithm for prime factorisation (I suspect it works better if the number is composite with many prime factors as well). Suggestions for improvements are welcome.
FastFactorise.py
def fact(n):
"""
* Function to factorise a given number given a list of prime numbers up to the square root of the number.
* Parameters:
* `n`: The number to be factorised.
* Return:
* `res`: A dict mapping each factor to its power in the prime factorisation of the number.
* Algorithm:
* Step 1: Initialise `res` to an empty dictionary.
* Step 2: If `n` > 1.
* Step 3: Iterate through the prime number list.
* Step 4: If ever the current prime number is > the floor of the square root of `n` + 1 exit the loop.
* Step 5: If the current prime number is a factor of `n`.
* Step 6: Assign 0 to `e`.
* Step 7: While the current prime number is a factor of `n`.
* Step 8: Increment `e`.
* Step 9: Divide `n` by the current prime number.
* [End of Step 7 while loop.]
* Step 10: Map the current prime number to `e` in the result dictionary.
* [End of step 5 if block.]
* Step 11: If `n` is not 1 (after the repeated dividings) map `n` to 1 in the result dictionary.
* Step 12: Return the result dictionary.
* [Exit the function.]
"""
res = {}
if n > 1:
for p in primes:
if p > int(sqrt(n)) + 1: break
if n%p == 0:
e = 0
while n%p == 0:
e += 1
n //= p
res[p] = e
if n != 1: res[n] = 1
return res
python performance beginner algorithm primes
python performance beginner algorithm primes
edited 4 hours ago
Jamal♦
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
edited 4 hours ago
Jamal♦
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
edited 4 hours ago
Jamal♦
30.3k11118227
edited 4 hours ago
Jamal♦
30.3k11118227
edited 4 hours ago
Jamal♦
30.3k11118227
30.3k11118227
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
asked 5 hours ago
Tobi AlafinTobi Alafin
28017
28017
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
sqrt is expensive. You can avoid it by reworking your test condition from:
p > int(sqrt(n)) + 1
to:
p*p > n
You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:
if n%p == 0:
e = 1
n //= p
while n%p == 0:
# ...etc...
Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.
The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
$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%2f213420%2ffast-factorisation-python-implementation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
sqrt is expensive. You can avoid it by reworking your test condition from:
p > int(sqrt(n)) + 1
to:
p*p > n
You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:
if n%p == 0:
e = 1
n //= p
while n%p == 0:
# ...etc...
Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.
The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
$endgroup$
add a comment |
$begingroup$
sqrt is expensive. You can avoid it by reworking your test condition from:
p > int(sqrt(n)) + 1
to:
p*p > n
You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:
if n%p == 0:
e = 1
n //= p
while n%p == 0:
# ...etc...
Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.
The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
$endgroup$
add a comment |
$begingroup$
sqrt is expensive. You can avoid it by reworking your test condition from:
p > int(sqrt(n)) + 1
to:
p*p > n
You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:
if n%p == 0:
e = 1
n //= p
while n%p == 0:
# ...etc...
Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.
The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
$endgroup$
sqrt is expensive. You can avoid it by reworking your test condition from:
p > int(sqrt(n)) + 1
to:
p*p > n
You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:
if n%p == 0:
e = 1
n //= p
while n%p == 0:
# ...etc...
Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.
The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
answered 1 hour ago
AJNeufeldAJNeufeld
5,297419
5,297419
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%2f213420%2ffast-factorisation-python-implementation%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
