Question

Describe to me a procedure for finding the prime factors of any number, in simple steps.

Answer 1

bonus if I can actually execute it in Python.

Answer 2

Python is executable pseudocode

Answer 3

this is simple man .. what have you tried ?

Answer 4

I can do it in pseudo-c, but not python.

for (i=1; i<sqrt{x}; i++)
{
if x%i == 0
{
cout << x << " is not prime, yo! " << ;
}
}

Answer 5

@Dalvoron:Incorrect solution

Answer 6

that's just the test for primality, not code for prime factorization. :-P

Answer 7

Aha, misread!

Answer 8

def primef(n):
i = 2
ans = []
while n > 1:
if n % i == 0:
n /= i
ans.append(i)
else:
for i in xrange(i, n+1):
if i**2 < n and n % i == 0:
break
return ans

is this right?

Answer 9

for prime numbers it just returns the prime number alone

Answer 10

It's not very optimized :(

Answer 11

the prime factorization of 999 is 3, 3, 3, and 37

Answer 12

The prime factorization of 24389 is 29*29*29

Answer 13

the prime factorization of 23897235782673 is :
OverflowError: Python int too large to convert to C long

Answer 14

how do I fix it?

Answer 15

what's your purpose for solving this problem?

Answer 16

just for fun :-D I wanna know a great way of doing it.

Answer 17

then I can port it to my calculator as an efficient C program.

Answer 18

I have a very optimized solution using miller rabin and pollard rho but it's for

www.spoj.pl/problems/FACT0/
www.spoj.pl/problems/FACT2/
www.spoj.pl/problems/FACT1/

Hence, I can't post here

Answer 19

:(

Answer 20

how do I fix my int too large for C long problem

Answer 21

that's exactly what the spoj problem is about.

Answer 22

so I need to write a bigint class if I am ever gonna port it to C?

Answer 23

Yes

Answer 24

but that would slow things down a little :( walk through the linked list

Answer 25

No.. learn properly first :)

Answer 26

http://stackoverflow.com/questions/1482480/xrange2100-overflowerror-long-int-too-large-to-convert-to-int

Answer 27

I've found nice libraries http://sourceforge.net/projects/msieve/