how do I find prime factors of a number

Is there a formula that I can use to find the prime factors of a given number?

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

On 28 Nov 2005 19:17:55 -0800, "DOR" <declanor1@cox.net> wrote:

>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

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

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

On 28 Nov 2005 20:37:04 -0800, "DOR" <declanor1@cox.net> wrote:

>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

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

"Gord Dibben" wrote
> 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
--
Rgds
Max
xl 97
---
Singapore, GMT+8
xdemechanik
http://savefile.com/projects/236895
--

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

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 :>)
--
Dana DeLouis
Win XP & Office 2003


"Gord Dibben" <gorddibbATshawDOTca> wrote in message
news:h6nno15p8n3380uvfovajkb6e229n9vgf9@4ax.com...
> 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
>
> On 28 Nov 2005 20:37:04 -0800, "DOR" <declanor1@cox.net> wrote:
>
>>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
>

On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis" <delouis@bellsouth.net>
wrote:

>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

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.
--
Gary's Student


"Jeff" wrote:

> Is there a formula that I can use to find the prime factors of a given number?

> 1234567890
> -- 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" <ronrosenfeld@nospam.org> wrote in message
news:bg1po1h5s3f1nb5jocfc28c9sspsjok39f@4ax.com...
> On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis" <delouis@bellsouth.net>
> wrote:
>
>>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

Thanks Max.

Gord

On Tue, 29 Nov 2005 13:55:28 +0800, "Max" <demechanik@yahoo.com> wrote:

>"Gord Dibben" wrote
>> 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
>--
>Rgds
>Max
>xl 97
>---
>Singapore, GMT+8
>xdemechanik
>http://savefile.com/projects/236895

Thanks Dana.

Squirrelled away ....with attribution.


Gord

On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis" <delouis@bellsouth.net>
wrote:

>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 :>)

<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.





On Tue, 29 Nov 2005 13:06:44 -0500, "Dana DeLouis" <delouis@bellsouth.net>
wrote:

>> 1234567890
>> -- 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?

--ron

"Ron Rosenfeld" <ronrosenfeld@nospam.org> wrote in message
news:9k9po19ofbqldq2hef9qjsuqgna2j440pd@4ax.com
> <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.

On Wed, 30 Nov 2005 17:28:27 +1300, "Alan" <alan@alan.alan> wrote:

>That would be because putting a 0 on the end is the same as
>multiplying by 10?
>
>Alan.
>

No question about it.
--ron

I developed a worksheet that gives the prime factorization for any number whose prime factors are all less than 100. When I input 4500, the output
it gives is:
2*2*3*3*5*5*5 (2 squared * 3 squared * 5 cubed )

This is an XLSM that factors out the primes of integers. With a little code manipulation, you can generate more or less values, up to the first 100000 integers.

If you add more primes, you can go beyond the 100k.