Mixing
Algorithms for Finding the Prime Factorization of an Integer
up vote
15
down vote
favorite
As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite.
My question is about algorithms: are there preferred algorithms for doing this? I've heard that factoring is a tricky business.
What I'm doing currently is that I use a prime sieve to find the primes $leq sqrt{n}$, then I loop through the list of primes (starting from $2$), checking divisibility --- if divisible, I write that prime to a list of prime factors, divide the integer by the prime, and begin looping through the list of primes again, checking divisibility of the updated integer.
This seems like a naive and inefficient approach. What methods would be more effective? What number-theoretic facts should I use to shortcut calculations?
elementary-number-theory algorithms
asked Jan 8 '14 at 16:46
Newb
13.2k93777
add a comment |
up vote
15
down vote
favorite
As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite.
My question is about algorithms: are there preferred algorithms for doing this? I've heard that factoring is a tricky business.
What I'm doing currently is that I use a prime sieve to find the primes $leq sqrt{n}$, then I loop through the list of primes (starting from $2$), checking divisibility --- if divisible, I write that prime to a list of prime factors, divide the integer by the prime, and begin looping through the list of primes again, checking divisibility of the updated integer.
This seems like a naive and inefficient approach. What methods would be more effective? What number-theoretic facts should I use to shortcut calculations?
elementary-number-theory algorithms
asked Jan 8 '14 at 16:46
Newb
13.2k93777
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
1
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37
add a comment |
up vote
15
down vote
favorite
up vote
15
down vote
favorite
As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite.
My question is about algorithms: are there preferred algorithms for doing this? I've heard that factoring is a tricky business.
What I'm doing currently is that I use a prime sieve to find the primes $leq sqrt{n}$, then I loop through the list of primes (starting from $2$), checking divisibility --- if divisible, I write that prime to a list of prime factors, divide the integer by the prime, and begin looping through the list of primes again, checking divisibility of the updated integer.
This seems like a naive and inefficient approach. What methods would be more effective? What number-theoretic facts should I use to shortcut calculations?
elementary-number-theory algorithms
asked Jan 8 '14 at 16:46
Newb
13.2k93777
As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite.
My question is about algorithms: are there preferred algorithms for doing this? I've heard that factoring is a tricky business.
What I'm doing currently is that I use a prime sieve to find the primes $leq sqrt{n}$, then I loop through the list of primes (starting from $2$), checking divisibility --- if divisible, I write that prime to a list of prime factors, divide the integer by the prime, and begin looping through the list of primes again, checking divisibility of the updated integer.
This seems like a naive and inefficient approach. What methods would be more effective? What number-theoretic facts should I use to shortcut calculations?
elementary-number-theory algorithms
elementary-number-theory algorithms
asked Jan 8 '14 at 16:46
Newb
13.2k93777
asked Jan 8 '14 at 16:46
Newb
13.2k93777
edited Jan 8 '14 at 17:18
asked Jan 8 '14 at 16:46
Newb
13.2k93777
asked Jan 8 '14 at 16:46
Newb
13.2k93777
asked Jan 8 '14 at 16:46
Newb
13.2k93777
13.2k93777
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
1
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37
add a comment |
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
1
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
1
1
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37
add a comment |
6 Answers
6
active
oldest
votes
up vote
7
down vote
A useful and fairly easy to implement integer factorization algorithm is Pollard's Rho Algorithm. You can supplement it with trial division or another factorization method in case the rho algorithm fails to find a nontrivial divisor, and in any case you will want to also implement a primality testing algorithm (I like a deterministic version of Miller-Rabin, which is guaranteed to work for most numbers and, depending on the version, for all numbers up to a large limit) to verify when the factors you have found are prime.
answered Jan 8 '14 at 17:10
universalset
7,3311230
add a comment |
up vote
4
down vote
I've been working on an identical problem. What I've learned so far is that determining the primality of a number is very difficult but also that prime factorization is even more difficult (computationally). Currently, I only have my "Prime Factorization Algorithm" perform trial division on $n$ for primes in the sequence $2,3,5,7,11,...,sqrt{n}$ because anything over the square root of $n$ will necessarily have a factor below $sqrt{n}$ too. The only exceptions are input values of $n$ which are perfect squares (i.e., 4,9,16,25,...) because $sqrt{n}$ itself accounts for one of the factors. This algorithm is nested in the same way you describe yours; that is, after finding a prime, take the quotient and repeat the process and storing each new prime as it comes along. Though this algorithm does not run in polynomial time, it is straightforward to program and entirely deterministic (as opposed to using probabilistic primality tests for larger values of $n$).
My primary concern right now is not factoring arbitrary inputs for $n$, but rather generating the list of primes up to and including $sqrt{n}$ and this is not trivial. I'm currently working to store each new prime as I generate it. But there are some ways to make this prime-number-generator work faster if you know:
- All prime numbers (greater than or equal to 7) end in a 1,3,7,9.
- All primes greater than $c$ can be represented in the form $ck+i$. You might be familiar with the simple example that primes over 6 can be represented as $6k+1$ or $6k+5$. Certain values of $c$ work more "efficiently" than others: through my empirical tests and some research I have found that Primorial numbers are usually good $c$ values (2,6,30,210,2310,etc. - click here for Wikipedia's take on Primality Tests and look for the paragraph that starts with the phrase "Generalizing further...")
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
add a comment |
up vote
2
down vote
You have not made much of a distinction about large numbers or small numbers; for the moment small numbers are good enough. At some point I realized I wanted a C++ command to factor any 32 bit signed integer, so absolute value up to $2^{31} - 1$ or 2,147,483,647. If I have an integer variable named n I can print it and its factorization with cout << n << Factored(n) << endl based on the code below
example stand alone program:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./factor
number to be factored ? 35283528
= 2^3 * 3^2 * 7^2 * 73 * 137
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(int i)
{
string fac;
fac = " = ";
int p = 2;
int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
Note that, in dealing with larger numbers, canned programs generally do such trial division up to some prime bound. My Factored printing command above finishes the job for small numbers, as I said, including a final possible largest prime factor called "temp." In the earliest years of Mathematica, they first did trial division with all primes up to $2^{31/2}$ or about 46,340. If that did not finish the job, other methods were attempted. So, one thing you could do now is to save a list of the primes up to 46,340, and report what happens when all those are pulled out of your big number, as I did. Then you can think about what to do with the leftover factor (my 'temp'), which could be prime or composite.
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
add a comment |
up vote
0
down vote
Don't loop over the primes again; you have already checked most of them (if they did not divide the original number, they won't divide the quotient). When you find a prime that divides your number, write that prime to a list, divide the integer by that prime, then continue through the list of primes from where you left off (making sure to repeat the one you just added to the list). You can also stop once your primes are bigger than the square root of the current quotient you are working with.
There are much better factoring algorithms but the best (number field sieve) involves a good amount of algebraic number theory.
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
add a comment |
up vote
0
down vote
What I do on my calculator: (pseudocode)
For prime variable A until sqrt(X)
If A divides X
Then
Divide X by A
Print A
Repeat loop resuming from A
Print X
This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X.
If the test variable A is greater than sqrt(X), then print X because it's prime.
answered May 26 '16 at 14:40
Bob Kerman
1
add a comment |
up vote
0
down vote
For background, please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
With some simple modifications to the Python program, we obtain a factorization algorithm that implements the Sieve of Eratosthenes as a recursive (mathematical definition) function.
Here is the Python code:
def PrimeSieve(curNum, inNumb):
prime = True
addSet = set()
for cp in PrimeRelations:
daPrime, daSkip = cp
if curNum == daSkip:
prime = False
addSet.add((daPrime, daSkip + daPrime))
if curNum == inNumb: # last integer being poccessed
inNumbPrimeFactors.add( daPrime )
if prime:
addSet.add((curNum, curNum + curNum))
PrimeRelations.update(addSet)
return prime
while True:
inNumb = int(input('Integer to be factored = '))
PrimeRelations = set()
inNumbPrimeFactors = set() # Populated w/ the prime factors of inNumb
# For inNumb = 63, inNumbPrimeFactors = {3, 7}
for intgr in range(2, inNumb + 1): isPrime = PrimeSieve(intgr, inNumb)
inNumb_factrztion = set()
if isPrime: # last processed intgr = inNumb
inNumb_factrztion.add( (inNumb, 1) )
else:
unfactored = inNumb
for p in inNumbPrimeFactors:
exp = 0
r = 0
while r == 0:
xxfactored, r = divmod(unfactored, p)
if r == 0:
exp = exp + 1
unfactored = xxfactored
else:
inNumb_factrztion.add( (p, exp) )
print('The prime factrztion of', inNumb, 'is given by', inNumb_factrztion)
* OUTPUT *
Integer to be factored = 2
The prime factorization of 2 is given by {(2, 1)}
Integer to be factored = 4
The prime factorization of 4 is given by {(2, 2)}
Integer to be factored = 72
The prime factorization of 72 is given by {(3, 2), (2, 3)}
Integer to be factored = 10403
The prime factorization of 10403 is given by {(101, 1), (103, 1)}
answered yesterday
CopyPasteIt
3,7071527
add a comment |
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
A useful and fairly easy to implement integer factorization algorithm is Pollard's Rho Algorithm. You can supplement it with trial division or another factorization method in case the rho algorithm fails to find a nontrivial divisor, and in any case you will want to also implement a primality testing algorithm (I like a deterministic version of Miller-Rabin, which is guaranteed to work for most numbers and, depending on the version, for all numbers up to a large limit) to verify when the factors you have found are prime.
answered Jan 8 '14 at 17:10
universalset
7,3311230
add a comment |
up vote
7
down vote
A useful and fairly easy to implement integer factorization algorithm is Pollard's Rho Algorithm. You can supplement it with trial division or another factorization method in case the rho algorithm fails to find a nontrivial divisor, and in any case you will want to also implement a primality testing algorithm (I like a deterministic version of Miller-Rabin, which is guaranteed to work for most numbers and, depending on the version, for all numbers up to a large limit) to verify when the factors you have found are prime.
answered Jan 8 '14 at 17:10
universalset
7,3311230
add a comment |
up vote
7
down vote
up vote
7
down vote
A useful and fairly easy to implement integer factorization algorithm is Pollard's Rho Algorithm. You can supplement it with trial division or another factorization method in case the rho algorithm fails to find a nontrivial divisor, and in any case you will want to also implement a primality testing algorithm (I like a deterministic version of Miller-Rabin, which is guaranteed to work for most numbers and, depending on the version, for all numbers up to a large limit) to verify when the factors you have found are prime.
answered Jan 8 '14 at 17:10
universalset
7,3311230
A useful and fairly easy to implement integer factorization algorithm is Pollard's Rho Algorithm. You can supplement it with trial division or another factorization method in case the rho algorithm fails to find a nontrivial divisor, and in any case you will want to also implement a primality testing algorithm (I like a deterministic version of Miller-Rabin, which is guaranteed to work for most numbers and, depending on the version, for all numbers up to a large limit) to verify when the factors you have found are prime.
answered Jan 8 '14 at 17:10
universalset
7,3311230
answered Jan 8 '14 at 17:10
universalset
7,3311230
answered Jan 8 '14 at 17:10
universalset
7,3311230
answered Jan 8 '14 at 17:10
universalset
7,3311230
7,3311230
add a comment |
add a comment |
up vote
4
down vote
I've been working on an identical problem. What I've learned so far is that determining the primality of a number is very difficult but also that prime factorization is even more difficult (computationally). Currently, I only have my "Prime Factorization Algorithm" perform trial division on $n$ for primes in the sequence $2,3,5,7,11,...,sqrt{n}$ because anything over the square root of $n$ will necessarily have a factor below $sqrt{n}$ too. The only exceptions are input values of $n$ which are perfect squares (i.e., 4,9,16,25,...) because $sqrt{n}$ itself accounts for one of the factors. This algorithm is nested in the same way you describe yours; that is, after finding a prime, take the quotient and repeat the process and storing each new prime as it comes along. Though this algorithm does not run in polynomial time, it is straightforward to program and entirely deterministic (as opposed to using probabilistic primality tests for larger values of $n$).
My primary concern right now is not factoring arbitrary inputs for $n$, but rather generating the list of primes up to and including $sqrt{n}$ and this is not trivial. I'm currently working to store each new prime as I generate it. But there are some ways to make this prime-number-generator work faster if you know:
- All prime numbers (greater than or equal to 7) end in a 1,3,7,9.
- All primes greater than $c$ can be represented in the form $ck+i$. You might be familiar with the simple example that primes over 6 can be represented as $6k+1$ or $6k+5$. Certain values of $c$ work more "efficiently" than others: through my empirical tests and some research I have found that Primorial numbers are usually good $c$ values (2,6,30,210,2310,etc. - click here for Wikipedia's take on Primality Tests and look for the paragraph that starts with the phrase "Generalizing further...")
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
add a comment |
up vote
4
down vote
I've been working on an identical problem. What I've learned so far is that determining the primality of a number is very difficult but also that prime factorization is even more difficult (computationally). Currently, I only have my "Prime Factorization Algorithm" perform trial division on $n$ for primes in the sequence $2,3,5,7,11,...,sqrt{n}$ because anything over the square root of $n$ will necessarily have a factor below $sqrt{n}$ too. The only exceptions are input values of $n$ which are perfect squares (i.e., 4,9,16,25,...) because $sqrt{n}$ itself accounts for one of the factors. This algorithm is nested in the same way you describe yours; that is, after finding a prime, take the quotient and repeat the process and storing each new prime as it comes along. Though this algorithm does not run in polynomial time, it is straightforward to program and entirely deterministic (as opposed to using probabilistic primality tests for larger values of $n$).
My primary concern right now is not factoring arbitrary inputs for $n$, but rather generating the list of primes up to and including $sqrt{n}$ and this is not trivial. I'm currently working to store each new prime as I generate it. But there are some ways to make this prime-number-generator work faster if you know:
- All prime numbers (greater than or equal to 7) end in a 1,3,7,9.
- All primes greater than $c$ can be represented in the form $ck+i$. You might be familiar with the simple example that primes over 6 can be represented as $6k+1$ or $6k+5$. Certain values of $c$ work more "efficiently" than others: through my empirical tests and some research I have found that Primorial numbers are usually good $c$ values (2,6,30,210,2310,etc. - click here for Wikipedia's take on Primality Tests and look for the paragraph that starts with the phrase "Generalizing further...")
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
add a comment |
up vote
4
down vote
up vote
4
down vote
I've been working on an identical problem. What I've learned so far is that determining the primality of a number is very difficult but also that prime factorization is even more difficult (computationally). Currently, I only have my "Prime Factorization Algorithm" perform trial division on $n$ for primes in the sequence $2,3,5,7,11,...,sqrt{n}$ because anything over the square root of $n$ will necessarily have a factor below $sqrt{n}$ too. The only exceptions are input values of $n$ which are perfect squares (i.e., 4,9,16,25,...) because $sqrt{n}$ itself accounts for one of the factors. This algorithm is nested in the same way you describe yours; that is, after finding a prime, take the quotient and repeat the process and storing each new prime as it comes along. Though this algorithm does not run in polynomial time, it is straightforward to program and entirely deterministic (as opposed to using probabilistic primality tests for larger values of $n$).
My primary concern right now is not factoring arbitrary inputs for $n$, but rather generating the list of primes up to and including $sqrt{n}$ and this is not trivial. I'm currently working to store each new prime as I generate it. But there are some ways to make this prime-number-generator work faster if you know:
- All prime numbers (greater than or equal to 7) end in a 1,3,7,9.
- All primes greater than $c$ can be represented in the form $ck+i$. You might be familiar with the simple example that primes over 6 can be represented as $6k+1$ or $6k+5$. Certain values of $c$ work more "efficiently" than others: through my empirical tests and some research I have found that Primorial numbers are usually good $c$ values (2,6,30,210,2310,etc. - click here for Wikipedia's take on Primality Tests and look for the paragraph that starts with the phrase "Generalizing further...")
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
I've been working on an identical problem. What I've learned so far is that determining the primality of a number is very difficult but also that prime factorization is even more difficult (computationally). Currently, I only have my "Prime Factorization Algorithm" perform trial division on $n$ for primes in the sequence $2,3,5,7,11,...,sqrt{n}$ because anything over the square root of $n$ will necessarily have a factor below $sqrt{n}$ too. The only exceptions are input values of $n$ which are perfect squares (i.e., 4,9,16,25,...) because $sqrt{n}$ itself accounts for one of the factors. This algorithm is nested in the same way you describe yours; that is, after finding a prime, take the quotient and repeat the process and storing each new prime as it comes along. Though this algorithm does not run in polynomial time, it is straightforward to program and entirely deterministic (as opposed to using probabilistic primality tests for larger values of $n$).
My primary concern right now is not factoring arbitrary inputs for $n$, but rather generating the list of primes up to and including $sqrt{n}$ and this is not trivial. I'm currently working to store each new prime as I generate it. But there are some ways to make this prime-number-generator work faster if you know:
- All prime numbers (greater than or equal to 7) end in a 1,3,7,9.
- All primes greater than $c$ can be represented in the form $ck+i$. You might be familiar with the simple example that primes over 6 can be represented as $6k+1$ or $6k+5$. Certain values of $c$ work more "efficiently" than others: through my empirical tests and some research I have found that Primorial numbers are usually good $c$ values (2,6,30,210,2310,etc. - click here for Wikipedia's take on Primality Tests and look for the paragraph that starts with the phrase "Generalizing further...")
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
answered Jan 8 '14 at 17:22
Xoque55
2,69131329
2,69131329
add a comment |
add a comment |
up vote
2
down vote
You have not made much of a distinction about large numbers or small numbers; for the moment small numbers are good enough. At some point I realized I wanted a C++ command to factor any 32 bit signed integer, so absolute value up to $2^{31} - 1$ or 2,147,483,647. If I have an integer variable named n I can print it and its factorization with cout << n << Factored(n) << endl based on the code below
example stand alone program:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./factor
number to be factored ? 35283528
= 2^3 * 3^2 * 7^2 * 73 * 137
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(int i)
{
string fac;
fac = " = ";
int p = 2;
int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
Note that, in dealing with larger numbers, canned programs generally do such trial division up to some prime bound. My Factored printing command above finishes the job for small numbers, as I said, including a final possible largest prime factor called "temp." In the earliest years of Mathematica, they first did trial division with all primes up to $2^{31/2}$ or about 46,340. If that did not finish the job, other methods were attempted. So, one thing you could do now is to save a list of the primes up to 46,340, and report what happens when all those are pulled out of your big number, as I did. Then you can think about what to do with the leftover factor (my 'temp'), which could be prime or composite.
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
add a comment |
up vote
2
down vote
You have not made much of a distinction about large numbers or small numbers; for the moment small numbers are good enough. At some point I realized I wanted a C++ command to factor any 32 bit signed integer, so absolute value up to $2^{31} - 1$ or 2,147,483,647. If I have an integer variable named n I can print it and its factorization with cout << n << Factored(n) << endl based on the code below
example stand alone program:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./factor
number to be factored ? 35283528
= 2^3 * 3^2 * 7^2 * 73 * 137
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(int i)
{
string fac;
fac = " = ";
int p = 2;
int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
Note that, in dealing with larger numbers, canned programs generally do such trial division up to some prime bound. My Factored printing command above finishes the job for small numbers, as I said, including a final possible largest prime factor called "temp." In the earliest years of Mathematica, they first did trial division with all primes up to $2^{31/2}$ or about 46,340. If that did not finish the job, other methods were attempted. So, one thing you could do now is to save a list of the primes up to 46,340, and report what happens when all those are pulled out of your big number, as I did. Then you can think about what to do with the leftover factor (my 'temp'), which could be prime or composite.
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
add a comment |
up vote
2
down vote
up vote
2
down vote
You have not made much of a distinction about large numbers or small numbers; for the moment small numbers are good enough. At some point I realized I wanted a C++ command to factor any 32 bit signed integer, so absolute value up to $2^{31} - 1$ or 2,147,483,647. If I have an integer variable named n I can print it and its factorization with cout << n << Factored(n) << endl based on the code below
example stand alone program:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./factor
number to be factored ? 35283528
= 2^3 * 3^2 * 7^2 * 73 * 137
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(int i)
{
string fac;
fac = " = ";
int p = 2;
int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
Note that, in dealing with larger numbers, canned programs generally do such trial division up to some prime bound. My Factored printing command above finishes the job for small numbers, as I said, including a final possible largest prime factor called "temp." In the earliest years of Mathematica, they first did trial division with all primes up to $2^{31/2}$ or about 46,340. If that did not finish the job, other methods were attempted. So, one thing you could do now is to save a list of the primes up to 46,340, and report what happens when all those are pulled out of your big number, as I did. Then you can think about what to do with the leftover factor (my 'temp'), which could be prime or composite.
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
You have not made much of a distinction about large numbers or small numbers; for the moment small numbers are good enough. At some point I realized I wanted a C++ command to factor any 32 bit signed integer, so absolute value up to $2^{31} - 1$ or 2,147,483,647. If I have an integer variable named n I can print it and its factorization with cout << n << Factored(n) << endl based on the code below
example stand alone program:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./factor
number to be factored ? 35283528
= 2^3 * 3^2 * 7^2 * 73 * 137
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(int i)
{
string fac;
fac = " = ";
int p = 2;
int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
Note that, in dealing with larger numbers, canned programs generally do such trial division up to some prime bound. My Factored printing command above finishes the job for small numbers, as I said, including a final possible largest prime factor called "temp." In the earliest years of Mathematica, they first did trial division with all primes up to $2^{31/2}$ or about 46,340. If that did not finish the job, other methods were attempted. So, one thing you could do now is to save a list of the primes up to 46,340, and report what happens when all those are pulled out of your big number, as I did. Then you can think about what to do with the leftover factor (my 'temp'), which could be prime or composite.
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
edited Jan 8 '14 at 19:54
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
answered Jan 8 '14 at 19:38
Will Jagy
100k597198
100k597198
add a comment |
add a comment |
up vote
0
down vote
Don't loop over the primes again; you have already checked most of them (if they did not divide the original number, they won't divide the quotient). When you find a prime that divides your number, write that prime to a list, divide the integer by that prime, then continue through the list of primes from where you left off (making sure to repeat the one you just added to the list). You can also stop once your primes are bigger than the square root of the current quotient you are working with.
There are much better factoring algorithms but the best (number field sieve) involves a good amount of algebraic number theory.
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
add a comment |
up vote
0
down vote
Don't loop over the primes again; you have already checked most of them (if they did not divide the original number, they won't divide the quotient). When you find a prime that divides your number, write that prime to a list, divide the integer by that prime, then continue through the list of primes from where you left off (making sure to repeat the one you just added to the list). You can also stop once your primes are bigger than the square root of the current quotient you are working with.
There are much better factoring algorithms but the best (number field sieve) involves a good amount of algebraic number theory.
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
add a comment |
up vote
0
down vote
up vote
0
down vote
Don't loop over the primes again; you have already checked most of them (if they did not divide the original number, they won't divide the quotient). When you find a prime that divides your number, write that prime to a list, divide the integer by that prime, then continue through the list of primes from where you left off (making sure to repeat the one you just added to the list). You can also stop once your primes are bigger than the square root of the current quotient you are working with.
There are much better factoring algorithms but the best (number field sieve) involves a good amount of algebraic number theory.
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
Don't loop over the primes again; you have already checked most of them (if they did not divide the original number, they won't divide the quotient). When you find a prime that divides your number, write that prime to a list, divide the integer by that prime, then continue through the list of primes from where you left off (making sure to repeat the one you just added to the list). You can also stop once your primes are bigger than the square root of the current quotient you are working with.
There are much better factoring algorithms but the best (number field sieve) involves a good amount of algebraic number theory.
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
answered Sep 28 '15 at 9:08
Morgan Rodgers
9,52521338
9,52521338
add a comment |
add a comment |
up vote
0
down vote
What I do on my calculator: (pseudocode)
For prime variable A until sqrt(X)
If A divides X
Then
Divide X by A
Print A
Repeat loop resuming from A
Print X
This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X.
If the test variable A is greater than sqrt(X), then print X because it's prime.
answered May 26 '16 at 14:40
Bob Kerman
1
add a comment |
up vote
0
down vote
What I do on my calculator: (pseudocode)
For prime variable A until sqrt(X)
If A divides X
Then
Divide X by A
Print A
Repeat loop resuming from A
Print X
This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X.
If the test variable A is greater than sqrt(X), then print X because it's prime.
answered May 26 '16 at 14:40
Bob Kerman
1
add a comment |
up vote
0
down vote
up vote
0
down vote
What I do on my calculator: (pseudocode)
For prime variable A until sqrt(X)
If A divides X
Then
Divide X by A
Print A
Repeat loop resuming from A
Print X
This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X.
If the test variable A is greater than sqrt(X), then print X because it's prime.
answered May 26 '16 at 14:40
Bob Kerman
1
What I do on my calculator: (pseudocode)
For prime variable A until sqrt(X)
If A divides X
Then
Divide X by A
Print A
Repeat loop resuming from A
Print X
This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X.
If the test variable A is greater than sqrt(X), then print X because it's prime.
answered May 26 '16 at 14:40
Bob Kerman
1
answered May 26 '16 at 14:40
Bob Kerman
1
answered May 26 '16 at 14:40
Bob Kerman
1
answered May 26 '16 at 14:40
Bob Kerman
1
1
add a comment |
add a comment |
up vote
0
down vote
For background, please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
With some simple modifications to the Python program, we obtain a factorization algorithm that implements the Sieve of Eratosthenes as a recursive (mathematical definition) function.
Here is the Python code:
def PrimeSieve(curNum, inNumb):
prime = True
addSet = set()
for cp in PrimeRelations:
daPrime, daSkip = cp
if curNum == daSkip:
prime = False
addSet.add((daPrime, daSkip + daPrime))
if curNum == inNumb: # last integer being poccessed
inNumbPrimeFactors.add( daPrime )
if prime:
addSet.add((curNum, curNum + curNum))
PrimeRelations.update(addSet)
return prime
while True:
inNumb = int(input('Integer to be factored = '))
PrimeRelations = set()
inNumbPrimeFactors = set() # Populated w/ the prime factors of inNumb
# For inNumb = 63, inNumbPrimeFactors = {3, 7}
for intgr in range(2, inNumb + 1): isPrime = PrimeSieve(intgr, inNumb)
inNumb_factrztion = set()
if isPrime: # last processed intgr = inNumb
inNumb_factrztion.add( (inNumb, 1) )
else:
unfactored = inNumb
for p in inNumbPrimeFactors:
exp = 0
r = 0
while r == 0:
xxfactored, r = divmod(unfactored, p)
if r == 0:
exp = exp + 1
unfactored = xxfactored
else:
inNumb_factrztion.add( (p, exp) )
print('The prime factrztion of', inNumb, 'is given by', inNumb_factrztion)
* OUTPUT *
Integer to be factored = 2
The prime factorization of 2 is given by {(2, 1)}
Integer to be factored = 4
The prime factorization of 4 is given by {(2, 2)}
Integer to be factored = 72
The prime factorization of 72 is given by {(3, 2), (2, 3)}
Integer to be factored = 10403
The prime factorization of 10403 is given by {(101, 1), (103, 1)}
answered yesterday
CopyPasteIt
3,7071527
add a comment |
up vote
0
down vote
For background, please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
With some simple modifications to the Python program, we obtain a factorization algorithm that implements the Sieve of Eratosthenes as a recursive (mathematical definition) function.
Here is the Python code:
def PrimeSieve(curNum, inNumb):
prime = True
addSet = set()
for cp in PrimeRelations:
daPrime, daSkip = cp
if curNum == daSkip:
prime = False
addSet.add((daPrime, daSkip + daPrime))
if curNum == inNumb: # last integer being poccessed
inNumbPrimeFactors.add( daPrime )
if prime:
addSet.add((curNum, curNum + curNum))
PrimeRelations.update(addSet)
return prime
while True:
inNumb = int(input('Integer to be factored = '))
PrimeRelations = set()
inNumbPrimeFactors = set() # Populated w/ the prime factors of inNumb
# For inNumb = 63, inNumbPrimeFactors = {3, 7}
for intgr in range(2, inNumb + 1): isPrime = PrimeSieve(intgr, inNumb)
inNumb_factrztion = set()
if isPrime: # last processed intgr = inNumb
inNumb_factrztion.add( (inNumb, 1) )
else:
unfactored = inNumb
for p in inNumbPrimeFactors:
exp = 0
r = 0
while r == 0:
xxfactored, r = divmod(unfactored, p)
if r == 0:
exp = exp + 1
unfactored = xxfactored
else:
inNumb_factrztion.add( (p, exp) )
print('The prime factrztion of', inNumb, 'is given by', inNumb_factrztion)
* OUTPUT *
Integer to be factored = 2
The prime factorization of 2 is given by {(2, 1)}
Integer to be factored = 4
The prime factorization of 4 is given by {(2, 2)}
Integer to be factored = 72
The prime factorization of 72 is given by {(3, 2), (2, 3)}
Integer to be factored = 10403
The prime factorization of 10403 is given by {(101, 1), (103, 1)}
answered yesterday
CopyPasteIt
3,7071527
add a comment |
up vote
0
down vote
up vote
0
down vote
For background, please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
With some simple modifications to the Python program, we obtain a factorization algorithm that implements the Sieve of Eratosthenes as a recursive (mathematical definition) function.
Here is the Python code:
def PrimeSieve(curNum, inNumb):
prime = True
addSet = set()
for cp in PrimeRelations:
daPrime, daSkip = cp
if curNum == daSkip:
prime = False
addSet.add((daPrime, daSkip + daPrime))
if curNum == inNumb: # last integer being poccessed
inNumbPrimeFactors.add( daPrime )
if prime:
addSet.add((curNum, curNum + curNum))
PrimeRelations.update(addSet)
return prime
while True:
inNumb = int(input('Integer to be factored = '))
PrimeRelations = set()
inNumbPrimeFactors = set() # Populated w/ the prime factors of inNumb
# For inNumb = 63, inNumbPrimeFactors = {3, 7}
for intgr in range(2, inNumb + 1): isPrime = PrimeSieve(intgr, inNumb)
inNumb_factrztion = set()
if isPrime: # last processed intgr = inNumb
inNumb_factrztion.add( (inNumb, 1) )
else:
unfactored = inNumb
for p in inNumbPrimeFactors:
exp = 0
r = 0
while r == 0:
xxfactored, r = divmod(unfactored, p)
if r == 0:
exp = exp + 1
unfactored = xxfactored
else:
inNumb_factrztion.add( (p, exp) )
print('The prime factrztion of', inNumb, 'is given by', inNumb_factrztion)
* OUTPUT *
Integer to be factored = 2
The prime factorization of 2 is given by {(2, 1)}
Integer to be factored = 4
The prime factorization of 4 is given by {(2, 2)}
Integer to be factored = 72
The prime factorization of 72 is given by {(3, 2), (2, 3)}
Integer to be factored = 10403
The prime factorization of 10403 is given by {(101, 1), (103, 1)}
answered yesterday
CopyPasteIt
3,7071527
For background, please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
With some simple modifications to the Python program, we obtain a factorization algorithm that implements the Sieve of Eratosthenes as a recursive (mathematical definition) function.
Here is the Python code:
def PrimeSieve(curNum, inNumb):
prime = True
addSet = set()
for cp in PrimeRelations:
daPrime, daSkip = cp
if curNum == daSkip:
prime = False
addSet.add((daPrime, daSkip + daPrime))
if curNum == inNumb: # last integer being poccessed
inNumbPrimeFactors.add( daPrime )
if prime:
addSet.add((curNum, curNum + curNum))
PrimeRelations.update(addSet)
return prime
while True:
inNumb = int(input('Integer to be factored = '))
PrimeRelations = set()
inNumbPrimeFactors = set() # Populated w/ the prime factors of inNumb
# For inNumb = 63, inNumbPrimeFactors = {3, 7}
for intgr in range(2, inNumb + 1): isPrime = PrimeSieve(intgr, inNumb)
inNumb_factrztion = set()
if isPrime: # last processed intgr = inNumb
inNumb_factrztion.add( (inNumb, 1) )
else:
unfactored = inNumb
for p in inNumbPrimeFactors:
exp = 0
r = 0
while r == 0:
xxfactored, r = divmod(unfactored, p)
if r == 0:
exp = exp + 1
unfactored = xxfactored
else:
inNumb_factrztion.add( (p, exp) )
print('The prime factrztion of', inNumb, 'is given by', inNumb_factrztion)
* OUTPUT *
Integer to be factored = 2
The prime factorization of 2 is given by {(2, 1)}
Integer to be factored = 4
The prime factorization of 4 is given by {(2, 2)}
Integer to be factored = 72
The prime factorization of 72 is given by {(3, 2), (2, 3)}
Integer to be factored = 10403
The prime factorization of 10403 is given by {(101, 1), (103, 1)}
answered yesterday
CopyPasteIt
3,7071527
edited yesterday
answered yesterday
CopyPasteIt
3,7071527
answered yesterday
CopyPasteIt
3,7071527
answered yesterday
CopyPasteIt
3,7071527
3,7071527
add a comment |
add a comment |
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%2fmath.stackexchange.com%2fquestions%2f631559%2falgorithms-for-finding-the-prime-factorization-of-an-integer%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
The simplest extension to your algorithm is to use Fermat's Factorization Method (en.wikipedia.org/wiki/Fermat's_factorization_method) and looking for differences of squares. In general, there are better methods than either a prime sieve or Fermat's method. Also, your prime sieve is very inefficient. You only need to check up to the square root of $n$.
– Foo Barrigno
Jan 8 '14 at 16:54
Have you looked at the Wikipedia article about integer factoring algorithms?
– fkraiem
Jan 8 '14 at 17:05
1
How big can $n$ be?
– TonyK
Jan 8 '14 at 20:30
This is basically the problem that got me into computer programming.
– Celeritas
Apr 2 '16 at 9:37