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
performance beginner algorithm primes
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
$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
performance beginner algorithm primes
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
$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
performance beginner algorithm primes
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
$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
performance beginner algorithm primes
performance beginner algorithm primes
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
asked 4 mins ago
Tobi AlafinTobi Alafin
26517
26517
add a comment |
add a comment |
0
active
oldest
votes
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
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
