Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Jeff
 
Posts: n/a
Default 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?
  #2   Report Post  
Posted to microsoft.public.excel.worksheet.functions
DOR
 
Posts: n/a
Default how do I find prime factors of a 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

  #3   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Ron Rosenfeld
 
Posts: n/a
Default how do I find prime factors of a number

On 28 Nov 2005 19:17:55 -0800, "DOR" 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
  #4   Report Post  
Posted to microsoft.public.excel.worksheet.functions
DOR
 
Posts: n/a
Default how do I find prime factors of a number

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

  #5   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Gord Dibben
 
Posts: n/a
Default how do I find prime factors of a number

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




  #6   Report Post  
Posted to microsoft.public.excel.worksheet.functions
DOR
 
Posts: n/a
Default how do I find prime factors of a number

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

  #7   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Max
 
Posts: n/a
Default how do I find prime factors of a number

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


  #8   Report Post  
Posted to microsoft.public.excel.worksheet.functions
DOR
 
Posts: n/a
Default how do I find prime factors of a number

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

  #9   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Dana DeLouis
 
Posts: n/a
Default how do I find prime factors of a number

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




  #10   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Ron Rosenfeld
 
Posts: n/a
Default how do I find prime factors of a number

On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis"
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


  #11   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Gary''s Student
 
Posts: n/a
Default how do I find prime factors of a number

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?

  #12   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Dana DeLouis
 
Posts: n/a
Default how do I find prime factors of a 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 a
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" wrote in message
...
On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis"
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




  #13   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Gord Dibben
 
Posts: n/a
Default how do I find prime factors of a number

Thanks Max.

Gord

On Tue, 29 Nov 2005 13:55:28 +0800, "Max" 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


  #14   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Gord Dibben
 
Posts: n/a
Default how do I find prime factors of a number

Thanks Dana.

Squirrelled away ....with attribution.


Gord

On Tue, 29 Nov 2005 10:43:01 -0500, "Dana DeLouis"
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 :)


  #15   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Ron Rosenfeld
 
Posts: n/a
Default how do I find prime factors of a number

<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"
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 a
2,3,3,5,3607, 3803.

I show one `5`. These factors check with another program. What numbers did
you get?


--ron


  #16   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Alan
 
Posts: n/a
Default how do I find prime factors of a number

"Ron Rosenfeld" wrote in message

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


  #17   Report Post  
Posted to microsoft.public.excel.worksheet.functions
Ron Rosenfeld
 
Posts: n/a
Default how do I find prime factors of a number

On Wed, 30 Nov 2005 17:28:27 +1300, "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
Reply
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
How do I find the sum of all digits in a number? monkeyforce5 Excel Discussion (Misc queries) 4 September 9th 05 09:49 PM
How do I find a missing number in a sequence of numbers? Nash Excel Worksheet Functions 2 August 11th 05 04:22 AM
Find the number of rows returned in a filter Tony W Excel Discussion (Misc queries) 5 May 30th 05 10:36 PM
How do I find highest number in a row and change color? pamstolen Excel Worksheet Functions 3 January 18th 05 01:35 AM
How do I find the first value in a column less than a number? redeucer Excel Worksheet Functions 6 November 4th 04 10:59 PM


All times are GMT +1. The time now is 12:01 PM.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright ©2004-2024 ExcelBanter.
The comments are property of their posters.
 

About Us

"It's about Microsoft Excel"