Prime Factorization With Java and Finding an Upper Bound

Question

Here is what I am looking to do. I have listed my code below for your reference. Thank you in advance for any help you can provide.

Goal: Find Prime Factorizations of a number n. Then concatenate the prime factors into one number, x. Then Take that number, x, and divide by n. If x%n = 0, print True. If x%n != 0, print false. (i.e. if n = 100, Prime Factors are 2,2,5,5. Turn into 2255, then take 2255/100. 2255%100 != 0, Print False. )

What I have now prints out the prime factors correctly for some numbers, but when I try to use another prime number, the program will quit. Also, If I use a number like 123, it will only print out 3, not 3 and 41. Do you have any suggestions?

If possible, ideally I would like to run this for numbers j= 2 through any upper bound I set, call the upper bound U, and if any value for j = 2 through U yields a result that is true (from above) Then I would like to print that j value.

import acm.program.*;
import acm.util.*;
import java.util.Scanner;
import java.util.Arrays.*;
// -------------------------------------------------------------------------

public class FactorsLoop extends ConsoleProgram
{
//~ Instance/static variables .............................................
private RandomGenerator rgen = RandomGenerator.getInstance();
//~ Constructor ...........................................................
// ----------------------------------------------------------
/**
 * Creates a new ForLoops object.
 */
public void run()
{
    // 


    int n1 = 10000;
    int n2 =(n1);

    double U = 10000;
    StringBuilder factors = new StringBuilder();
    for (int j = 2; j < U; j++) {

        for (int i = 2; i*i <= n1; i++) {
            // if i is a factor of N, repeatedly divide it out
            while (n1% i == 0) {

                n1 = n1 / i;


                factors.append(Integer.toString(i));

            }

        }

    }

    double newNumber = Integer.parseInt(factors.toString());

    double x = (newNumber / n2);

    print(x);

    if ( newNumber % n2 == 0 ){
        println(n2);    
    }
}

}

Possible duplicate of [Largest prime factor of a number in Java](http://stackoverflow.com/questions/34353648/largest-prime-factor-of-a-number-in-java) — pczeus, Mar 26 '16 at 20:30

DarthGizka · Accepted Answer · 2016-03-26T22:35:49.310

Your code correctly adds all those primes to factors which it divides out. However, it also should add n1 after the loop, should it happen to be != 1 (which will occur precisely when the power of the largest factor is 1).

The reason is the optimisation in your code whereby the inner loop is exited when the current factor exceeds sqrt(n1) (condition i*i <= n1 in the for loop header). This is a valid optimisation but like many optimisations it makes the logic more complicated and error-prone...

Note: the outer loop that iterates j does not seem to make any sense at all; it will only cause the small factors to be appended repeatedly. Get the inner loop into working shape, factor it out into a separate function (pun intended) and then use it to implement your ranged test which looks for the first result that satisfies some criterion.

For example, the function that returns the concatenated factors could look like this:

public string concatenated_factors (int n)
{
    StringBuilder result = new StringBuilder();

    for (int i = 2; i * i <= n; ++i)
        for ( ; n % i == 0; n /= i)
            result.append(Integer.toString(i));

    if (n != 1)
        result.append(Integer.toString(n));

    return result.toString();
}

Note: I'm not familiar with Java, so some specifics may be a bit fuzzy here.

Where would I add the n1 after the loop? after the While loop, or after the for loop? And are you saying if i*i != 1, or if n1%i != 1? Would you mind showing me by just copying the portion of my code that you are talking about? Thanks for the reply by the way. — L Brunot, Mar 26 '16 at 22:16
@L Brunot: done. P.S.: please remember to accept my answer if you find that it answers your question sufficiently. And please have a quick look at the [tour page](http://stackoverflow.com/tour) to get an overview and to see why voting questions, answers and comments is important. — DarthGizka, Mar 26 '16 at 22:30

Prime Factorization With Java and Finding an Upper Bound

1 Answers1