Re: Any Better logic for this problem..
On Thu, Jun 9, 2011 at 6:10 PM, Dan Stromberg drsali...@gmail.com wrote:
On Thu, Jun 9, 2011 at 10:55 AM, geremy condra debat...@gmail.com wrote:
On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel da...@ieee.org wrote:
On 01/-10/-28163 02:59 PM, Chris Rebert wrote:
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
sganapathy.subraman...@gmail.com wrote:
Hi Guru's,
I'm working on a solution to find the prime factor of the number
This part of the code works.. http://www.pastie.org/2041584
When the number gets bigger, the range cannot iterate through bigger
number
and it does not work.
When I googled , I came across creating our own range function to
solve
this. I was just wondering if there was a better algorithm to get the
prime
numbers / prime factors of a long number?
Any inputs is highly appreciated.
Others have pointed out various inefficiencies. But I wanted to start by
asking what this is for. Do you really have a need to factor numbers
over 2
billion? Repeatedly? In multiple runs of the program? Do you have
weeks
of computer time to spend or just hours? Are you really interested in
the
factors, or just whether or not a particular large number is prime
(==has
anyfactors) ? If this is a homework assignment, what's the exact
assignment? Are you permitted to use other libraries, or other
languages?
Are you permitted to use language features you haven't encountered yet
in
class?
My solution:
def factors(x):
status, output = subprocess.getstatusoutput('factor %d' % x)
if not status:
return [int(i) for i in output.split()[1:]]
else:
print(output)
Works pretty well.
snip
So you should probably turn the problem around. Design a function that
calculates the nth prime, but that caches the work it's already done (on
disk if appropriate, but in a list if not). In the loop that's finding
the
factors, simply call the first function each time, and each time you
find a
factor, divide num by that so you're dealing with a smaller number.
Just use a precomputed table to do your trial division. There's a list
of the first fifty million primes on prime pages- if you aren't
dealing with specially constructed values (ie, RSA moduli) and haven't
found a factor by the end of the first ten thousand or so you probably
need to do a primality check before moving on to trying to factor it.
Geremy Condra
--
http://mail.python.org/mailman/listinfo/python-list
You Might be able to benefit from a primality test like Miller-Rabin, at
least if your numbers can be really large. It can answer with this number
is definitely composite or this number is probably prime. For quite
large numbers, it might speed things up. For smaller numbers, trial
division is faster.
I have a Python Miller-Rabin module at:
http://stromberg.dnsalias.org/svn/big-prime/trunk/
Here's a non-gmpy randomized MR implementation:
import random
def miller_rabin(n, confidence=20):
t, s, d = n-1, 0, 0
while not t % 2:
t = t 1
s += 1
t, d = n-1, t
for i in range(confidence):
a = random.randrange(2, n)
x = pow(a, d, n)
if x == 1: continue
if x == t: continue
for r in range(1, s):
x = pow(x, 2, n)
if x == t: break
if x == 1: return False
else: return False
return True
--
http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium sganapathy.subraman...@gmail.com wrote: Hi Guru's, I'm working on a solution to find the prime factor of the number This part of the code works.. http://www.pastie.org/2041584 For the archives, that code is: num = 13195 #num = 600851475143L prime_numbers = [2] prime_factors = [] for i in range (2,num): for j in prime_numbers: if i % j == 0: break else: prime_numbers.append(i) print 'The Prime Numbers are : ', prime_numbers for items in prime_numbers: if num % items == 0: prime_factors.append(items) print 'The prime factors are : ' , prime_factors In the future, please avoid the unnecessary indirection of pastebins when your code is relatively short. Including the code directly in your post is also likely to increase the response rate you get. Cheers, Chris When the number gets bigger, the range cannot iterate through bigger number and it does not work. When I googled , I came across creating our own range function to solve this. I was just wondering if there was a better algorithm to get the prime numbers / prime factors of a long number? Any inputs is highly appreciated. -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On 09/06/2011 09:31, Ganapathy Subramanium wrote: Hi Guru's, I'm working on a solution to find the prime factor of the number This part of the code works.. http://www.pastie.org/2041584 When the number gets bigger, the range cannot iterate through bigger number and it does not work. When I googled , I came across creating our own range function to solve this. I was just wondering if there was a better algorithm to get the prime numbers / prime factors of a long number? Any inputs is highly appreciated. If I was attempting this problem, I would pre-compute a file of prime numbers, in increasing order (probably use the Sieve of Erastothenes approach). You need a list of primes from 2 to the square root of the largest num you will have to process. With that, you simply work through the prime numbers, Divide num by this prime. If no remainder, replace num with num // prime (so you divide by the same prime again). else step on to next prime without changing num Stop when num becomes 1. e.g. 50 divides by 2 so factors are (2) and 25 into next iteration with 3 25 which won't divide by 3,so factors remain (2) and 25 goes into next iteration with 5 25 // 5 is 5 so factors become (2,5) and 5 into next iteration with 5 5 // 5 is 1so factors are (2,5,5) and computation complete. Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On Thu, Jun 9, 2011 at 7:06 PM, Chris Rebert c...@rebertia.com wrote: On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium sganapathy.subraman...@gmail.com wrote: Hi Guru's, I'm working on a solution to find the prime factor of the number This part of the code works.. http://www.pastie.org/2041584 For the archives, that code is: for items in prime_numbers: if num % items == 0: prime_factors.append(items) print 'The prime factors are : ' , prime_factors Prime factors don't quite work that way. The prime factors of 24, for instance, are 2, 2, 2, and 3. But if you're looking for _unique_ prime factors, then this will work. Rather than find all prime numbers up to num, stop at sqrt(num) - it's not possible to have any prime factors larger than that. (Be sure to include the square root itself; range(2,sqrt(num)) won't work if num is a perfect square. Use range(2,sqrt(num)+1) for safety.) That will save a fair amount of effort. Also, if you divide num by each factor found, it'll make the numbers smaller, which may be faster. Hope that helps! Chris Angelico -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On 01/-10/-28163 02:59 PM, Chris Rebert wrote: On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium sganapathy.subraman...@gmail.com wrote: Hi Guru's, I'm working on a solution to find the prime factor of the number This part of the code works.. http://www.pastie.org/2041584 For the archives, that code is: num =3195 #num =00851475143L prime_numbers =2] prime_factors =] for i in range (2,num): for j in prime_numbers: if i % j =0: break else: prime_numbers.append(i) print 'The Prime Numbers are : ', prime_numbers for items in prime_numbers: if num % items =0: prime_factors.append(items) print 'The prime factors are : ' , prime_factors In the future, please avoid the unnecessary indirection of pastebins when your code is relatively short. Including the code directly in your post is also likely to increase the response rate you get. Cheers, Chris When the number gets bigger, the range cannot iterate through bigger number and it does not work. When I googled , I came across creating our own range function to solve this. I was just wondering if there was a better algorithm to get the prime numbers / prime factors of a long number? Any inputs is highly appreciated. Others have pointed out various inefficiencies. But I wanted to start by asking what this is for. Do you really have a need to factor numbers over 2 billion? Repeatedly? In multiple runs of the program? Do you have weeks of computer time to spend or just hours? Are you really interested in the factors, or just whether or not a particular large number is prime (==has anyfactors) ? If this is a homework assignment, what's the exact assignment? Are you permitted to use other libraries, or other languages? Are you permitted to use language features you haven't encountered yet in class? Assuming you have to use pure python, no extra libraries, nothing complex, I'd just concentrate on making the current program efficient, without major surgery. First, you're generating far more primes than you can possibly need. You could stop at the square root of num. Next, you're trying every number, but you could be checking every other number (just add a step value to the range). Those two changes eliminate the range() problem, as the sqrt doesn't get over 2 billion till the num is over 10**18. But more fundamentally, you're generating a big list of numbers, using part of it once, and throwing it away. You could cache that list, store it on disk between runs, and make it tons faster. Worse you probably don't even need anywhere near the sqrt, unless num is prime. So you should probably turn the problem around. Design a function that calculates the nth prime, but that caches the work it's already done (on disk if appropriate, but in a list if not). In the loop that's finding the factors, simply call the first function each time, and each time you find a factor, divide num by that so you're dealing with a smaller number. There are faster ways to generate the primes, but now those optimizations can be applied to the nthprime() function, and they're independent of the factorization loop. DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel da...@ieee.org wrote:
On 01/-10/-28163 02:59 PM, Chris Rebert wrote:
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
sganapathy.subraman...@gmail.com wrote:
Hi Guru's,
I'm working on a solution to find the prime factor of the number
This part of the code works.. http://www.pastie.org/2041584
When the number gets bigger, the range cannot iterate through bigger
number
and it does not work.
When I googled , I came across creating our own range function to solve
this. I was just wondering if there was a better algorithm to get the
prime
numbers / prime factors of a long number?
Any inputs is highly appreciated.
Others have pointed out various inefficiencies. But I wanted to start by
asking what this is for. Do you really have a need to factor numbers over 2
billion? Repeatedly? In multiple runs of the program? Do you have weeks
of computer time to spend or just hours? Are you really interested in the
factors, or just whether or not a particular large number is prime (==has
anyfactors) ? If this is a homework assignment, what's the exact
assignment? Are you permitted to use other libraries, or other languages?
Are you permitted to use language features you haven't encountered yet in
class?
My solution:
def factors(x):
status, output = subprocess.getstatusoutput('factor %d' % x)
if not status:
return [int(i) for i in output.split()[1:]]
else:
print(output)
Works pretty well.
snip
So you should probably turn the problem around. Design a function that
calculates the nth prime, but that caches the work it's already done (on
disk if appropriate, but in a list if not). In the loop that's finding the
factors, simply call the first function each time, and each time you find a
factor, divide num by that so you're dealing with a smaller number.
Just use a precomputed table to do your trial division. There's a list
of the first fifty million primes on prime pages- if you aren't
dealing with specially constructed values (ie, RSA moduli) and haven't
found a factor by the end of the first ten thousand or so you probably
need to do a primality check before moving on to trying to factor it.
Geremy Condra
--
http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
Chris Angelico wrote: Rather than find all prime numbers up to num, stop at sqrt(num) - it's not possible to have any prime factors larger than that. That's not quite true -- the prime factors of 26 are 2 and 13, and 13 is clearly greater than sqrt(26). However, once you've divided out all the primes up to sqrt(n), whatever is left, if greater than 1, must itself be prime, so you can add it to your prime factors and stop. -- Greg -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On Fri, Jun 10, 2011 at 8:39 AM, Gregory Ewing greg.ew...@canterbury.ac.nz wrote: Chris Angelico wrote: Rather than find all prime numbers up to num, stop at sqrt(num) - it's not possible to have any prime factors larger than that. That's not quite true -- the prime factors of 26 are 2 and 13, and 13 is clearly greater than sqrt(26). Oops! My bad. I was thinking in terms of the divide and conquer algorithm, whereby the 13 would be the residuum after dividing by 2... However, once you've divided out all the primes up to sqrt(n), whatever is left, if greater than 1, must itself be prime, so you can add it to your prime factors and stop. ... which is effectively the same as you describe here. It's a small algorithmic change but an extremely advantageous one. If you _don't_ look for the residuum, then you stop at n/2 instead of sqrt(n). Either way, though, you don't need to list the primes all the way up to n, which will improve performance significantly. Chris Angelico -- http://mail.python.org/mailman/listinfo/python-list
Re: Any Better logic for this problem..
On Thu, Jun 9, 2011 at 10:55 AM, geremy condra debat...@gmail.com wrote:
On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel da...@ieee.org wrote:
On 01/-10/-28163 02:59 PM, Chris Rebert wrote:
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
sganapathy.subraman...@gmail.com wrote:
Hi Guru's,
I'm working on a solution to find the prime factor of the number
This part of the code works.. http://www.pastie.org/2041584
When the number gets bigger, the range cannot iterate through bigger
number
and it does not work.
When I googled , I came across creating our own range function to solve
this. I was just wondering if there was a better algorithm to get the
prime
numbers / prime factors of a long number?
Any inputs is highly appreciated.
Others have pointed out various inefficiencies. But I wanted to start by
asking what this is for. Do you really have a need to factor numbers
over 2
billion? Repeatedly? In multiple runs of the program? Do you have
weeks
of computer time to spend or just hours? Are you really interested in
the
factors, or just whether or not a particular large number is prime (==has
anyfactors) ? If this is a homework assignment, what's the exact
assignment? Are you permitted to use other libraries, or other
languages?
Are you permitted to use language features you haven't encountered yet
in
class?
My solution:
def factors(x):
status, output = subprocess.getstatusoutput('factor %d' % x)
if not status:
return [int(i) for i in output.split()[1:]]
else:
print(output)
Works pretty well.
snip
So you should probably turn the problem around. Design a function that
calculates the nth prime, but that caches the work it's already done (on
disk if appropriate, but in a list if not). In the loop that's finding
the
factors, simply call the first function each time, and each time you find
a
factor, divide num by that so you're dealing with a smaller number.
Just use a precomputed table to do your trial division. There's a list
of the first fifty million primes on prime pages- if you aren't
dealing with specially constructed values (ie, RSA moduli) and haven't
found a factor by the end of the first ten thousand or so you probably
need to do a primality check before moving on to trying to factor it.
Geremy Condra
--
http://mail.python.org/mailman/listinfo/python-list
You Might be able to benefit from a primality test like Miller-Rabin, at
least if your numbers can be really large. It can answer with this number
is definitely composite or this number is probably prime. For quite
large numbers, it might speed things up. For smaller numbers, trial
division is faster.
I have a Python Miller-Rabin module at:
http://stromberg.dnsalias.org/svn/big-prime/trunk/
--
http://mail.python.org/mailman/listinfo/python-list
