prime factors for large numbers












3














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)










share|improve this question






















  • Check up to the square root of x only.
    – 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
















3














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)










share|improve this question






















  • Check up to the square root of x only.
    – 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














3












3








3







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)










share|improve this question













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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 23 '18 at 12:14









Wybe TuringWybe Turing

334




334












  • Check up to the square root of x only.
    – 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






  • 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












1 Answer
1






active

oldest

votes


















3














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.






share|improve this answer





















  • Wow! What an improvement. Thanks.
    – Wybe Turing
    Nov 23 '18 at 14:36











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
});


}
});














draft saved

draft discarded


















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









3














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.






share|improve this answer





















  • Wow! What an improvement. Thanks.
    – Wybe Turing
    Nov 23 '18 at 14:36
















3














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.






share|improve this answer





















  • Wow! What an improvement. Thanks.
    – Wybe Turing
    Nov 23 '18 at 14:36














3












3








3






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.






share|improve this answer












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.







share|improve this answer












share|improve this answer



share|improve this answer










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


















  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

What visual should I use to simply compare current year value vs last year in Power BI desktop

How to ignore python UserWarning in pytest?

Alexandru Averescu