prime factors for large numbers
I wrote this to determine the largest prime factor of any given number. It works well for numbers with less than 9 digits but behaves in an indefinite manner when the number of digits goes beyond nine. How can I optimize it?
This function determines if a number is a prime number
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
This function determines if a number is a prime factor of another
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value
def functionFinal(x):
import math
factors =
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
print(time.process_time()-start_time)
python prime-factoring
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
add a comment |
I wrote this to determine the largest prime factor of any given number. It works well for numbers with less than 9 digits but behaves in an indefinite manner when the number of digits goes beyond nine. How can I optimize it?
This function determines if a number is a prime number
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
This function determines if a number is a prime factor of another
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value
def functionFinal(x):
import math
factors =
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
print(time.process_time()-start_time)
python prime-factoring
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
Check up to the square root ofxonly.
– Klaus D.
Nov 23 '18 at 12:17
1
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18
add a comment |
I wrote this to determine the largest prime factor of any given number. It works well for numbers with less than 9 digits but behaves in an indefinite manner when the number of digits goes beyond nine. How can I optimize it?
This function determines if a number is a prime number
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
This function determines if a number is a prime factor of another
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value
def functionFinal(x):
import math
factors =
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
print(time.process_time()-start_time)
python prime-factoring
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
I wrote this to determine the largest prime factor of any given number. It works well for numbers with less than 9 digits but behaves in an indefinite manner when the number of digits goes beyond nine. How can I optimize it?
This function determines if a number is a prime number
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
This function determines if a number is a prime factor of another
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value
def functionFinal(x):
import math
factors =
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
print(time.process_time()-start_time)
python prime-factoring
python prime-factoring
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
asked Nov 23 '18 at 12:14
Wybe TuringWybe Turing
334
334
Check up to the square root ofxonly.
– Klaus D.
Nov 23 '18 at 12:17
1
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18
add a comment |
Check up to the square root ofxonly.
– Klaus D.
Nov 23 '18 at 12:17
1
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18
Check up to the square root of
x only.– Klaus D.
Nov 23 '18 at 12:17
Check up to the square root of
x only.– Klaus D.
Nov 23 '18 at 12:17
1
1
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18
add a comment |
1 Answer
1
active
oldest
votes
You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
So, that
functionFinal(234675684)
has the performance comparison,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
add a comment |
Your Answer
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: "1"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fstackoverflow.com%2fquestions%2f53446542%2fprime-factors-for-large-numbers%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
You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
So, that
functionFinal(234675684)
has the performance comparison,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
add a comment |
You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
So, that
functionFinal(234675684)
has the performance comparison,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
add a comment |
You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
So, that
functionFinal(234675684)
has the performance comparison,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
So, that
functionFinal(234675684)
has the performance comparison,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
answered Nov 23 '18 at 12:45
Deepak SainiDeepak Saini
1,582814
1,582814
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
add a comment |
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
Wow! What an improvement. Thanks.
– Wybe Turing
Nov 23 '18 at 14:36
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fstackoverflow.com%2fquestions%2f53446542%2fprime-factors-for-large-numbers%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
Check up to the square root of
xonly.– Klaus D.
Nov 23 '18 at 12:17
1
You could fasten your prime number checker with function explained in this answer
– Filip Młynarski
Nov 23 '18 at 12:18