Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1198
  • 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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

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