[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1200
  • Last Modified:

need algorithm for finding factors of any number

I'm working on a program which factors polynomials: www.hampleman.com/quadeqfact.exe

I found a bug in the algorithm that factors numbers. If I input a number like 24 it breaks it down into a list of prime numbers: 2 * 2 * 2 * 3. Then it starts with the first in the list, mult by the remaining, adds it to the list of factors. The list of factors is a list of ordered pairs, each ordpair has 2 numbers which mult by each other, gets 24, in this case, then takes the first 2 in the list and mult by the rest. Then it takes the first 3 mult them together to get a list of (2,12) (4,6) (8,3) (1,24). This algorithm works fine for numbers like this, but for numbers like 2310 which breaks down to 2 * 3 * 5 * 7 * 11, I can't use this method because it doesn't try all possible combinations. I'm trying to think of an elegant solution that can try all possible combinations. Any suggestions?

Dan
0
zliminator
Asked:
zliminator
  • 4
1 Solution
 
zliminatorAuthor Commented:
I'm thinking of how the bits in a binary number are incremented:
In the case of 2310 = 2 * 3 * 5 * 7 * 11 use a 5 bit binary number and count from 00001 to 11110 like:
00001
00010
00011
00100
..
11100
11101
11110
In the case of 00011, the 0's represent 2 * 3 * 5 = 30 and the 1's represent 7 * 11 = 77.
0
 
zliminatorAuthor Commented:
but this would be inefficent in the case of 2 * 2 * 3 * 7 because of the 2^2
0
 
zliminatorAuthor Commented:
another note: we only need to go 1/2 way threw the binary list because:
00010 will give the same results as
11101
0
 
zliminatorAuthor Commented:
I've decided to just make an array of an array of booleans so that each sub array holds the binary pattern of the number 1 - 2^n where n = number of prime factors of the number to find factors for:
so that   each boolbinarray represents the binary number of 1's and 0's. My question now is: what's the most efficient way to implement this? Would bit shifting be to cumbersome?

  Public Sub MakeList()
        Dim binarray As ArrayList
        Dim boolbinarray As ArrayList
        Dim I As Integer = factorlist.Count
        Dim J As Int32 = Math.Pow(2, I)
        Dim K As Integer
        binarray = New ArrayList()
 
        For K = 0 To J - 1
            boolbinarray = New ArrayList()
 
            boolbinarray.Add()
 
            binarray.Add(boolbinarray)
        Next
    End Sub

Open in new window

0

Featured Post

[Webinar] Improve your customer journey

A positive customer journey is important in attracting and retaining business. To improve this experience, you can use Google Maps APIs to increase checkout conversions, boost user engagement, and optimize order fulfillment. Learn how in this webinar presented by Dito.

  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now