factoring problem


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 12 of 12

Thread: factoring problem

  1. #1
    Join Date
    Jan 2006
    Posts
    6

    Post factoring problem

    Hi,

    I am having trouble trying to factor 999999, i need to only print out the prime number factors of 999999 but right now I am just working on getting all the factors to printout. The first factor that is printed is 2 which obviously isn't correct because since I have both n and i declared as int. Then 3 isn't even printed which should be the first factor. Is this a problem in my first if statement? Please check my code, thanks for your help

    int n=999999;
    int i;
    for (i=2; i<37; i++)
    {

    if (n%i ==0);
    {
    System.out.print(i +" ");
    n=n/i;
    System.out.print(n +" ");
    i++;
    }
    if (n%i !=0)
    i++;
    }

  2. #2
    Join Date
    Feb 2006
    Posts
    11
    Factoring a number is actually fairly complicated. What does your algorithm look like? I think if you write it out, not only will it help us help you, but will help you figure out what you're doing wrong. (I couldn't clearly see where you're going. Something is wrong since you're looking that the modulus twice, when in your loop you should only need to do it once.)

  3. #3
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Sorry, I don't understand what you are trying to do...

    Take a look at this code... see if it helps:
    Code:
    
    public void printFactors(int n) {
        for (int i = 1; i < n / 2; i++) {
            if (n % i == 0) {
                System.out.println(i + " * " + (n / i));
            }
        }
    }
    Now, to print the prime factors, we only need to make a slight adjustment to our code:
    Code:
    
    public void printPrimeFactors(int n) {
        for (int i = 1; i < n / 2; i++) {
            if (n % i == 0 && isPrime(i)) {
                System.out.println(i + " * " + (n / i));
            }
        }
    }
    
    public boolean isPrime(int n) {
        // prime logic here
        return true;
    }
    Last edited by destin; 03-05-2006 at 09:57 PM.

  4. #4
    Join Date
    Jan 2006
    Posts
    6
    this is what my algorithm looks like.

    step n k comment
    ------------------------------------------------
    0 999999 2 not divisible by 2, k = k + 1
    1 999999 3 n is divisible by 3, n = n / 3, print 3
    2 333333 3 n is divisible by 3, n = n / 3, print 3
    3 111111 3 n is divisible by 3, n = n / 3, print 3
    4 37037 3 not divisible by 3, k = k + 1
    5 37037 4 not divisible by 4, k = k + 1
    6 37037 5 not divisible by 5, k = k + 1
    7 37037 6 not divisible by 6, k = k + 1
    8 37037 7 n is divisible by 7, n = n / 7, print 7
    9 5291 7 not divisible by 7, k = k + 1
    10 5291 8 not divisible by 8, k = k + 1
    11 5291 9 not divisible by 9, k = k + 1
    12 5291 10 not divisible by 10, k = k + 1
    13 5291 11 n is divisible by 11, n = n / 11, print 11
    14 481 11 not divisible by 11, k = k + 1
    15 481 12 not divisible by 12, k = k + 1
    16 481 13 n is divisible by 13, n = n / 13, print 13
    17 37 13 STOP since 13^2 > 37 print 37

  5. #5
    Join Date
    Jan 2006
    Posts
    6
    so to sum up - I need to print all the prime factors of 999999 using this type of algorith. I know I need a for statement to increment the k value (1-37) but after that I'm a bit lost. Hopefully you are not

  6. #6
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Hmm...

    Well, first thing that comes to mind to me is a recursive algorithm.
    Code:
    
        factor(999999)
        /             \
     add(3)    factor(333333)
                     /        \
                 add(3)   factor(111111)
                                  /    \
                          add(3)  factor(37037)
    .... etc

  7. #7
    Join Date
    Feb 2006
    Location
    Minnesota
    Posts
    33
    Well, just for starters, you have two BIG problems:

    [1] Your curly braces {} don't match up.

    [2] You're manipulating your loop counter "i" within the range of the for-loop.

    Whether the logic you're using to solve the math problem is correct is another issue entirely.

  8. #8
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Anyway, here's how to tackle my recursive algorithm.
    Code:
    
    private ArrayList<Integer> factors = new ArrayList<Integer>();
    
    public void addPrimeFactors(int n) {
        for (int i = 2; i < n / 2; i++) {
            if (n % i == 0 && isPrime(i)) {
                factors.add(i);
                addPrimeFactors(n / i);
                return;
            }
        }
    }
    This should work -- there is one problem I left for you to fix: it will not add the last prime factor (in this case, 37). Anyway, see if this makes sense to you, if not, take a different approach.

  9. #9
    Join Date
    Jan 2006
    Posts
    6
    we haven't learned arrays yet

  10. #10
    Join Date
    Jan 2006
    Posts
    6
    i still am having problems with the prime logic - i cant seem to get the factor that i got from the main method to get to the isPrime method...?

  11. #11
    Join Date
    Jul 2005
    Location
    the Netherlands
    Posts
    128
    Quote Originally Posted by xirix
    i still am having problems with the prime logic - i cant seem to get the factor that i got from the main method to get to the isPrime method...?
    You don't need an isPrime(...) method. Here's an example:
    Code:
    public class Test {
    
        public Test(int n) {
            while(n > 1) {
                for(int i = 2; i <= n; i++) {
                    if(n%i == 0) {
                        n = n/i;
                        System.out.println((n*i)+" = "+i+" * "+n);
                        break;
                    }
                }
            }
            System.out.println("done!");
        }
    
        public static void main(String[] args) {
            new Test(999999);
        }
    }

  12. #12
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Quote Originally Posted by prometheuzz
    You don't need an isPrime(...) method. Here's an example:
    Code:
    public class Test {
    
        public Test(int n) {
            while(n > 1) {
                for(int i = 2; i <= n; i++) {
                    if(n%i == 0) {
                        n = n/i;
                        System.out.println((n*i)+" = "+i+" * "+n);
                        break;
                    }
                }
            }
            System.out.println("done!");
        }
    
        public static void main(String[] args) {
            new Test(999999);
        }
    }
    Yeah, this was my first approach... I thought the other way might be easier to understand. Anyway, this was what I did:
    Code:
    
    public void printPrimeFactors(int n) {
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                System.out.println(i);
                n /= i;
                i = 2;
            }
        }
    }
    Which is really the same thing as yours

Similar Threads

  1. Problem with Search
    By Irina in forum ASP.NET
    Replies: 0
    Last Post: 11-29-2002, 11:47 PM
  2. Replies: 0
    Last Post: 12-13-2001, 01:06 PM
  3. a problem with font and language
    By Roseta in forum VB Classic
    Replies: 0
    Last Post: 11-14-2001, 04:24 AM
  4. Arabic problem view
    By Ayman in forum VB Classic
    Replies: 0
    Last Post: 04-03-2000, 02:08 AM
  5. Problem with CryptoAPI and JCE
    By Jason Bock in forum VB Classic
    Replies: 0
    Last Post: 03-21-2000, 07:48 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center