Find all Factors for Phony Numbers

0
votes

I am trying to find the quickest full factor algorithm. I use put all the factors into an arraylist for addition and compare the sum against the original number to find out if they are the same.

example. 6 has the factors of [1,2,3} if you add 1+2+3 = 6.

Is there a quicker way to factorize, add, and compare, other than the program i have now?

public class Phony_Number {

private int number;

public Phony_Number(int num) {
    number = num;
    print();
}

public Phony_Number() {
    number = 0;
}

private ArrayList<Integer> factoring(int num) {
    ArrayList<Integer> factors = new ArrayList<Integer>();
    if (num % 2 == 0) {
        for (int ff = 3; ff < num; ff++) {
            if (num % ff == 0) {
                factors.add(ff);
            }
        }
    }
    return factors;
}

private int sum(ArrayList<Integer> array) {
    int sum = 0;
    for (int i = 0; i < array.size(); i++) {
        sum = +sum + array.get(i);
    }
    return sum+3;
}

private boolean compare(int num, int sum) {
    if (num == sum)
        return true;
    return false;
}

public void print() {
    for (int i = number; i > 5; i--) {
        if (compare(i, sum(factoring(i)))) {
            System.out.println("Number " + i + " is phony number");
        }
    }
}

}

My current result for 20,000 numbers is this

Number 8128 is phony number

Number 496 is phony number

Number 28 is phony number

Number 6 is phony number

Nano RunTime 359624716
3
javaalgorithmruntimefactors
Is this a project Euler problem? - wvdz
By the way you are factoring only even numbers (you are sure Phony Numbers are all even?). You could Sieve primes until Sqrt(Limit), factoring in primes the number and generate divisors using the primes factorization. Could add cache of factorization in primes too. - NetVipeC
These numbers are called perfect numbers, not phony numbers, as you can find by searching the Online Encyclopedia of Integer Sequences for 6, 28, 496, 8128. The only even perfect numbers are of the form 2*2^n*(2^n-1) where 2^n-1 is prime, and it is a famous open problem whether there are odd perfect numbers, and you won't find any by a brute force search of small numbers. There are much faster ways to factor numbers than your trial division, or even the better approach of testing possible prime factors up to sqrt(n), but many are complicated. Try Pollard-rho factorization, for example. - Douglas Zare

3 Answers

1
votes

A few little things jumped out: Your compare method is pointless, remove that and it will simplify your code a little. Your sum method can just use +=. Why loop through every number then drop half of them, just use -=2 on the loop.

Your main saving though can come from your factoring method - you know that numbers over num/2 cannot be factors so you can stop as soon as you get to there.

(In fact in this case you may be able to stop at num/3 as you are skipping 2.

1
votes

As you're iterating through I believe you can get the co-factor as well by doing division. For example:

if (num % ff == 0) 
{
   factors.add(num/ff)
   factors.add(ff);
}

but you'll have to account for already adding them so I'm not positive if it helps in the long run.

You could also use:

return num == sum
1
votes

Divisors ff of num come in pairs, i.e. both ff and num/ff are divisors if ff is a divisor. Furthermore the divisors in the pair are distinct unless ff*ff == num. So you change your loop condition to ff*ff <= num, and then add ff to the factor list if ff divides num, and add num/ff as well if ff*ff != num. This will make your program run in square root of num time, instead of num time.