Talk:Prime factorization algorithm

From Wikipedia, the free encyclopedia

Can someone give me the python script which returns

$ python factorize.py 1800
[2^3, 3^2, 5^2]

instead of

$ python factorize.py 1800
[2, 2, 2, 3, 3, 5, 5]

import sys,math
def factorize(n):
    def isPrime(n):
        return not [x for x in xrange(2,int(math.sqrt(n)))
                    if n%x == 0]
    primes = []
    candidates = xrange(2,n+1)
    candidate = 2
    while not primes and candidate in candidates:
        if n%candidate == 0 and isPrime(candidate):
            primes = primes + [candidate] + factorize(n/candidate)
        candidate += 1            
    return primes

def condense(L):
  prime,count,list=0,0,[]
  for x in L:
    if x == prime:
      count = count + 1
    else:
      if prime != 0:
        list = list + [str(prime) + '^' + str(count)]
      prime,count=x,1
  list = list + [str(prime) + '^' + str(count)]
  return list

print factorize(int(sys.argv[1]))
print condense(factorize(int(sys.argv[1])))

---

$ python factorize.py 1800
[2, 2, 2, 3, 3, 5, 5]
['2^3', '3^2', '5^2']

[edit] some improvements of the code

The current sqrt() algorithm has limitations due to recursion. I've written a new one based on Square root that should run faster and accept larger values. Then I have rewritten the factorize() algorithm. The performance improvements here are marginal, I've just rewritten it for learning purposes. The source is available at [1]. Feel free to use it as you want.

[edit] C++ Example

If were going to have examples shouldn't they actually work? The C++ example wouldn't even compile, unless their is a new version of C++ that doesn't use namespaces or require an int return from main()? If you fix those minor errors however the example seesm to be putting out nonsense; id est, giving the same primes for output no matter what the input. I wish life were that easy. :D (I didn't check the logs, but I'm thinking this was originally a C example someone haphazardly converted to C++, or someone has a goat for a compiler.)

I'm putting it here until I or someone else can fix it.

#include <iostream>
#include <cmath>

using std::cout;
using std::endl;

int isPrime(int n)
{
  for(int ind=2;ind<=sqrt(n);ind++) {
    if (n%ind==0) {
      return true;
    }
  }
  return false;
}

int main(int argc, char *argv[])
{
  // check argc to make sure we recieved a value.

  int n = atoi(argv[1]);

  for(int i=2;i<=n;i++)
  {
    while ( !isPrime(i) && n%i == 0 )
    {
      cout << i << " ";
      n=n/i;
    }
  }
  cout << endl;

  return 0
}