G
Guest
Is there a formula that I can use to find the prime factors of a given number?
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
D
DOR
Try this, assuming number is in A1:
=LARGE((ROUND($A$1/ROW(INDIRECT("$1:$"&$A$1)),0)=$A$1/ROW(INDIRECT("$1:$"&$A$1)))*ROW(INDIRECT("$1:$"&$A$1)),ROW(1:1))
Enter as an array formula - Ctl+Shift+Enter and drag/copy down as far
as necessary to show all factors. Works for positive numbers only.
Would need to put ABS($A$1) for all instances of $A$1 if there was a
danger the number could be negative.
Declan O'R
=LARGE((ROUND($A$1/ROW(INDIRECT("$1:$"&$A$1)),0)=$A$1/ROW(INDIRECT("$1:$"&$A$1)))*ROW(INDIRECT("$1:$"&$A$1)),ROW(1:1))
Enter as an array formula - Ctl+Shift+Enter and drag/copy down as far
as necessary to show all factors. Works for positive numbers only.
Would need to put ABS($A$1) for all instances of $A$1 if there was a
danger the number could be negative.
Declan O'R
R
Ron Rosenfeld
Try this, assuming number is in A1:
=LARGE((ROUND($A$1/ROW(INDIRECT("$1:$"&$A$1)),0)=$A$1/ROW(INDIRECT("$1:$"&$A$1)))*ROW(INDIRECT("$1:$"&$A$1)),ROW(1:1))
Enter as an array formula - Ctl+Shift+Enter and drag/copy down as far
as necessary to show all factors. Works for positive numbers only.
Would need to put ABS($A$1) for all instances of $A$1 if there was a
danger the number could be negative.
Declan O'R
Your formula appears to produce *all* the factors for a given integer. I
believe the OP only wanted the *prime* factors.
--ron
D
DOR
The method I provided finds the *factors* of N, not the prime factors,
and only up to an N of 65,536 at that, unless you are willing to forego
N itself, in which case it can be modified to go higher, to 131,072.
Sorry about that, I didn't read your post properly. You can find a
method of finding factors here
http://tinyurl.com/dljjt
using VBA. This also has a macro for finding the primes up to a given
number. You may be able to combine the two methods to get the prime
factors.
FWIW, there is a program available here
http://tinyurl.com/aleae
for computing prime factors.
I hope THIS helps, as opposed to my previous post.
I'll take another look at it to see if I can find or determine another
approach.
Declan O'R
and only up to an N of 65,536 at that, unless you are willing to forego
N itself, in which case it can be modified to go higher, to 131,072.
Sorry about that, I didn't read your post properly. You can find a
method of finding factors here
http://tinyurl.com/dljjt
using VBA. This also has a macro for finding the primes up to a given
number. You may be able to combine the two methods to get the prime
factors.
FWIW, there is a program available here
http://tinyurl.com/aleae
for computing prime factors.
I hope THIS helps, as opposed to my previous post.
I'll take another look at it to see if I can find or determine another
approach.
Declan O'R
G
Gord Dibben
Grabbed this code from one of these news groups. Wish I could attribute, but
can't remember.
Run on new worksheet or one with nothing in Column A
Sub Listfactors()
Range("A1").Select
Dim Originalnumber As Long
Dim Factors() As Integer
Dim Counter As Integer
Dim Fact As Integer
Dim theRest As Long
Dim Formulastring As String
Originalnumber = CLng(Val(InputBox("Number:")))
theRest = Originalnumber
Counter = 0
ReDim Factors(0)
For Fact = 2 To Originalnumber
If theRest / Fact = Int(theRest / Fact) Then
ReDim Preserve Factors(Counter)
Factors(Counter) = Fact
Counter = Counter + 1
theRest = theRest / Fact
Fact = Fact - 1
End If
Next
Formulastring = "="
For Counter = LBound(Factors) To UBound(Factors)
Cells(Counter + 1, 1).Value = Factors(Counter)
Formulastring = Formulastring & _
Cells(Counter + 1, 1).Address & "*"
Next
Formulastring = Left(Formulastring, Len(Formulastring) - 1)
Cells(UBound(Factors) + 2, 1).Formula = Formulastring
End Sub
Gord Dibben Excel MVP
can't remember.
Run on new worksheet or one with nothing in Column A
Sub Listfactors()
Range("A1").Select
Dim Originalnumber As Long
Dim Factors() As Integer
Dim Counter As Integer
Dim Fact As Integer
Dim theRest As Long
Dim Formulastring As String
Originalnumber = CLng(Val(InputBox("Number:")))
theRest = Originalnumber
Counter = 0
ReDim Factors(0)
For Fact = 2 To Originalnumber
If theRest / Fact = Int(theRest / Fact) Then
ReDim Preserve Factors(Counter)
Factors(Counter) = Fact
Counter = Counter + 1
theRest = theRest / Fact
Fact = Fact - 1
End If
Next
Formulastring = "="
For Counter = LBound(Factors) To UBound(Factors)
Cells(Counter + 1, 1).Value = Factors(Counter)
Formulastring = Formulastring & _
Cells(Counter + 1, 1).Address & "*"
Next
Formulastring = Left(Formulastring, Len(Formulastring) - 1)
Cells(UBound(Factors) + 2, 1).Formula = Formulastring
End Sub
Gord Dibben Excel MVP
D
DOR
Thanks Ron. I realized that when I re-read the OP shortly after I
responded - I was formulating another message (while you responded.
The prime factors are a lot more difficult, and I've found no
excel-based solution ... food for thought.
Declan
responded - I was formulating another message (while you responded.
The prime factors are a lot more difficult, and I've found no
excel-based solution ... food for thought.
Declan
M
Max
Grabbed this code from one of these news groups.
Wish I could attribute, but can't remember...
Perhaps it was Harald Staff in .prog in early 2001 ? <g>,
re-this googled post: http://tinyurl.com/7f5qg
D
DOR
Nice find, Gord. It appears to have an upper limit in the 35,000 range,
probably due to the dimensions of the variables. That could probably
be adjusted by varying the data type definitions. Probably would be
useful to add some test for the upper limit on the input also, rather
than allowing an error in the execution.
DOR
probably due to the dimensions of the variables. That could probably
be adjusted by varying the data type definitions. Probably would be
useful to add some test for the upper limit on the input also, rather
than allowing an error in the execution.
DOR
D
Dana DeLouis
Perhaps a slight change to this excellent code might be:
For Fact = 2 To Sqr(OriginalNumber)
I was just messing around, and wrote a variation on this theme as follows:
The idea here was to skip 2 numbers at a time. (ie numbers ending in
1,3,5,7,9...)
Of course, checking 5 is a waste also, but it cuts the number of searches by
half.
Sub FactorInteger()
'// Needs: Microsoft Scripting Runtime
Dim Fact As Long
Dim TheRest As Long
Dim Limit As Long
Dim d As New Dictionary
TheRest = CLng(Val(InputBox("Number:")))
'// Just '2'
Do While TheRest / 2 = Int(TheRest / 2)
d.Add d.Count, 2
TheRest = TheRest / 2
Loop
Fact = 3
Limit = Sqr(TheRest)
Do Until TheRest = 1 Or Fact > Limit
If TheRest / Fact = Int(TheRest / Fact) Then
d.Add d.Count, Fact
TheRest = TheRest / Fact
Else
Fact = Fact + 2
End If
Loop
If TheRest > 1 Then d.Add d.Count, TheRest
[A:A].Clear
[A1].Resize(d.Count) = WorksheetFunction.Transpose(d.Items)
Cells(d.Count + 2, 1).FormulaR1C1 = "=Product(R1C:R[-2]C)"
End Sub
Looks like a good idea to limit variables to Long. Otherwise, using these
techniques, it may take a long time to factor a number
like 100000099999829 into 10000019 & 9999991.
HTH :>)
For Fact = 2 To Sqr(OriginalNumber)
I was just messing around, and wrote a variation on this theme as follows:
The idea here was to skip 2 numbers at a time. (ie numbers ending in
1,3,5,7,9...)
Of course, checking 5 is a waste also, but it cuts the number of searches by
half.
Sub FactorInteger()
'// Needs: Microsoft Scripting Runtime
Dim Fact As Long
Dim TheRest As Long
Dim Limit As Long
Dim d As New Dictionary
TheRest = CLng(Val(InputBox("Number:")))
'// Just '2'
Do While TheRest / 2 = Int(TheRest / 2)
d.Add d.Count, 2
TheRest = TheRest / 2
Loop
Fact = 3
Limit = Sqr(TheRest)
Do Until TheRest = 1 Or Fact > Limit
If TheRest / Fact = Int(TheRest / Fact) Then
d.Add d.Count, Fact
TheRest = TheRest / Fact
Else
Fact = Fact + 2
End If
Loop
If TheRest > 1 Then d.Add d.Count, TheRest
[A:A].Clear
[A1].Resize(d.Count) = WorksheetFunction.Transpose(d.Items)
Cells(d.Count + 2, 1).FormulaR1C1 = "=Product(R1C:R[-2]C)"
End Sub
Looks like a good idea to limit variables to Long. Otherwise, using these
techniques, it may take a long time to factor a number
like 100000099999829 into 10000019 & 9999991.
HTH :>)
R
Ron Rosenfeld
Perhaps a slight change to this excellent code might be:
For Fact = 2 To Sqr(OriginalNumber)
I was just messing around, and wrote a variation on this theme as follows:
The idea here was to skip 2 numbers at a time. (ie numbers ending in
1,3,5,7,9...)
Of course, checking 5 is a waste also, but it cuts the number of searches by
half.
Sub FactorInteger()
'// Needs: Microsoft Scripting Runtime
Dim Fact As Long
Dim TheRest As Long
Dim Limit As Long
Dim d As New Dictionary
TheRest = CLng(Val(InputBox("Number:")))
'// Just '2'
Do While TheRest / 2 = Int(TheRest / 2)
d.Add d.Count, 2
TheRest = TheRest / 2
Loop
Fact = 3
Limit = Sqr(TheRest)
Do Until TheRest = 1 Or Fact > Limit
If TheRest / Fact = Int(TheRest / Fact) Then
d.Add d.Count, Fact
TheRest = TheRest / Fact
Else
Fact = Fact + 2
End If
Loop
If TheRest > 1 Then d.Add d.Count, TheRest
[A:A].Clear
[A1].Resize(d.Count) = WorksheetFunction.Transpose(d.Items)
Cells(d.Count + 2, 1).FormulaR1C1 = "=Product(R1C:R[-2]C)"
End Sub
Looks like a good idea to limit variables to Long. Otherwise, using these
techniques, it may take a long time to factor a number
like 100000099999829 into 10000019 & 9999991.
HTH :>)
Hmmm.
1234567890
-- one of its prime factors is 5, but it is not returned by your algorithm.
--ron
G
Guest
See:
http://support.microsoft.com/?kbid=202782
An approach would be to first generate all prime numbers within Excel's 15
digit number space. Second, generate all the factors of a number. Lastly,
remove the non-prime ones.
http://support.microsoft.com/?kbid=202782
An approach would be to first generate all prime numbers within Excel's 15
digit number space. Second, generate all the factors of a number. Lastly,
remove the non-prime ones.
D
Dana DeLouis
1234567890
Hi Ron. If I input 1234567890, then the numbers I get for cells A1:A6 are:
2,3,3,5,3607, 3803.
I show one `5`. These factors check with another program. What numbers did
you get?
--
Dana DeLouis
Win XP & Office 2003
-- one of its prime factors is 5, but it is not returned by your
algorithm.
Hi Ron. If I input 1234567890, then the numbers I get for cells A1:A6 are:
2,3,3,5,3607, 3803.
I show one `5`. These factors check with another program. What numbers did
you get?
--
Dana DeLouis
Win XP & Office 2003
Ron Rosenfeld said:Perhaps a slight change to this excellent code might be:
For Fact = 2 To Sqr(OriginalNumber)
I was just messing around, and wrote a variation on this theme as follows:
The idea here was to skip 2 numbers at a time. (ie numbers ending in
1,3,5,7,9...)
Of course, checking 5 is a waste also, but it cuts the number of searches
by
half.
Sub FactorInteger()
'// Needs: Microsoft Scripting Runtime
Dim Fact As Long
Dim TheRest As Long
Dim Limit As Long
Dim d As New Dictionary
TheRest = CLng(Val(InputBox("Number:")))
'// Just '2'
Do While TheRest / 2 = Int(TheRest / 2)
d.Add d.Count, 2
TheRest = TheRest / 2
Loop
Fact = 3
Limit = Sqr(TheRest)
Do Until TheRest = 1 Or Fact > Limit
If TheRest / Fact = Int(TheRest / Fact) Then
d.Add d.Count, Fact
TheRest = TheRest / Fact
Else
Fact = Fact + 2
End If
Loop
If TheRest > 1 Then d.Add d.Count, TheRest
[A:A].Clear
[A1].Resize(d.Count) = WorksheetFunction.Transpose(d.Items)
Cells(d.Count + 2, 1).FormulaR1C1 = "=Product(R1C:R[-2]C)"
End Sub
Looks like a good idea to limit variables to Long. Otherwise, using these
techniques, it may take a long time to factor a number
like 100000099999829 into 10000019 & 9999991.
HTH :>)
Hmmm.
1234567890
-- one of its prime factors is 5, but it is not returned by your
algorithm.
--ron
G
Gord Dibben
Thanks Max.
Gord
Gord
Perhaps it was Harald Staff in .prog in early 2001 ? <g>,
re-this googled post: http://tinyurl.com/7f5qg
G
Gord Dibben
Thanks Dana.
Squirrelled away ....with attribution.
Gord
Squirrelled away ....with attribution.
Gord
R
Ron Rosenfeld
<sheepish look> I inputted the wrong number to be missing the '5'. After
rechecking, it turns out I was inputting 123456789 rather than 1234567890.
Of interest is that the prime factors for 123456789 are very similar. Just
eliminate the 2 and the 5.
Nice routine.
--ron
rechecking, it turns out I was inputting 123456789 rather than 1234567890.
Of interest is that the prime factors for 123456789 are very similar. Just
eliminate the 2 and the 5.
Nice routine.
Hi Ron. If I input 1234567890, then the numbers I get for cells A1:A6 are:
2,3,3,5,3607, 3803.
I show one `5`. These factors check with another program. What numbers did
you get?
--ron
A
Alan
Ron Rosenfeld said:<sheepish look> I inputted the wrong number to be missing the '5'.
After rechecking, it turns out I was inputting 123456789 rather than
1234567890.
Of interest is that the prime factors for 123456789 are very similar.
Just eliminate the 2 and the 5.
That would be because putting a 0 on the end is the same as
multiplying by 10?
Alan.
R
Ron Rosenfeld
That would be because putting a 0 on the end is the same as
multiplying by 10?
Alan.
No question about it.
--ron
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.