Solved

need algorithm for finding factors of any number

Posted on 2008-10-23
5
1,190 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
Comment
Question by:zliminator
  • 4
5 Comments
 

Author Comment

by:zliminator
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

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

Author Comment

by:zliminator
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

by:zliminator
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

Open in new window

0
 
LVL 84

Accepted Solution

by:
ozo earned 125 total points
ID: 22793799
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Need help with programming in R stats software 6 31
Java string tokenizing help on Fantasy Football 6 95
linearIn  challenge 23 84
Homework Math Question 1 88
Dependencies in Software Design In software development, the idea of dependencies (http://en.wikipedia.org/wiki/Coupling_%28computer_programming%29) is an issue of some importance. This article seeks to explain what dependencies are and where they …
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
As a trusted technology advisor to your customers you are likely getting the daily question of, ‘should I put this in the cloud?’ As customer demands for cloud services increases, companies will see a shift from traditional buying patterns to new…

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

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

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now