Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

need algorithm for finding factors of any number

Posted on 2008-10-23
Medium Priority
1,197 Views
Last Modified: 2013-11-12
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
Question by:zliminator
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 4
5 Comments

Author Comment

ID: 22785349
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

Author Comment

ID: 22785389
but this would be inefficent in the case of 2 * 2 * 3 * 7 because of the 2^2
0

Author Comment

ID: 22785954
another note: we only need to go 1/2 way threw the binary list because:
00010 will give the same results as
11101
0

Author Comment

ID: 22786736
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
``````
0

LVL 84

Accepted Solution

ozo earned 500 total points
ID: 22793799
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is Waterfall Model? Waterfall model is the classic Software Development Life Cycle method practiced in software development process. As the name "waterfall" describes, this development is flowing downwards steadily like waterfall, i.e., procee…
Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Want to learn how to record your desktop screen without having to use an outside camera. Click on this video and learn how to use the cool google extension called "Screencastify"! Step 1: Open a new google tab Step 2: Go to the left hand upper corn…
Suggested Courses
Course of the Month6 days, 9 hours left to enroll

704 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.