CareerCup

Here is a simple optimization explained using an example.

Lets say we need to find factors of 18

We create a set containing factors. Initially insert 1 to the set

Now we check if 18%2 == 0

If yes, we check if 2 exists in the set. It does not, so we insert 2 in the set.
Also, we check if 9 exists in the set (2X9==18) , it does not so we add 9 to the set

Similarly, while checking for 3, we add 3 and 6 to the set.

18%4!=0 and also 18%5!=0, so we dont add 4 and 5 to the set

Now while checking for 6 we notice that 6 already exists in the set. We terminate the process here since the set now contains all the factors.

Finally add n to the set.

Set : 1,2,9,3,6,18

void findfactors_rec(int n, int m)
{
    m = m - 1;

    if(m == 0)
        return;
    if(n % m == 0)
        printf("%d\n", m);

    findfactors_rec(n,m);
}

void findfactors_rec_wrapper(int n)
{
    findfactors_rec(n,n);
}

int main()
{
    findfactors_rec_wrapper(24);
}

Again use tail recursion. Linear recursion does not have the stack unwinding phase as large

dont get question correctly ??
is it all factor of a given number ??

def prime_factors(n):
	i = 2
	limit = n**0.5
	while i <= limit:
		if n % i == 0:
		  yield i
		  n = n / i
		  limit = n**0.5
		else:
		  i += 1
	if n > 1:
		yield n

def all_factors(n):
	from itertools import combinations
	pfs = tuple(prime_factors(n))
	for i in xrange(1,len(pfs)):
		for j in combinations(pfs,i):
			yield reduce(int.__mul__,j)

Hi oni ,
Can you please explain the logic.

1. Find all the prime factors
2. Find the all multiplication combinations for all factors using recursion

public class AllFactors {
    
    public static void main(String [] args) {
        int number = 15;
        List<Long> primeFactors = getUniquePrimes(number);
        List<Long> allFactors = new AllFactors().getAllFactors(primeFactors);
        System.out.println(allFactors);
    }
    
    List<Long> allFactorsBuffer = Lists.newArrayList();
    public List<Long> getAllFactors(List<Long> primeFactors) {
        recursiveGrouping(primeFactors, 0, 1);
        return Lists.newArrayList(allFactorsBuffer);
    }
    
    private void recursiveGrouping(List<Long> primeFactors, int position, long startValue) {
        if(position == primeFactors.size()) {
            allFactorsBuffer.add(startValue);
        }
        else {
            recursiveGrouping(primeFactors, position + 1, startValue * primeFactors.get(position));
            recursiveGrouping(primeFactors, position + 1, startValue);
        }
    }
    public static List<Long> getUniquePrimes(long number) {
        List<Long> uniquePrimes = new ArrayList<Long>();
        long primeDivisor = 0;
        long numberCopy = number;
        do {
            primeDivisor = getLeastPrimeDivisor(numberCopy, new ArrayList<Long>());
            if(primeDivisor != -1) {
                numberCopy = numberCopy/primeDivisor;
            }
            if(primeDivisor != -1) {
                uniquePrimes.add(primeDivisor);
            }
            if(primeDivisor == -1) {
                uniquePrimes.add(numberCopy);
            }
        } while(primeDivisor != -1);
        return uniquePrimes;
    }

    private static long getLeastPrimeDivisor(long number, List<Long> primeNumbers) {
        long halfNumber = number/2;
        for(long i = 2; i<= halfNumber; i++) {
            if(isPrime(i, primeNumbers)) {
                if(number%i == 0) {
                    return i;
                }
                else {
                    primeNumbers.add(i);
                }
            }
        }
        return -1;
    }

    private static boolean isPrime(long number, List<Long> primeNumbers) {
        long halfNumber = number/2;
        for(long prime: primeNumbers) {
            if(prime >= halfNumber) break;
            if(number%prime == 0) {
                return false;
            }
        }
        return true;
    }
}

void foo(int n,vector<int>& vv)
{
int lim=n;
for (int i=1; i<=lim; i++) {
if (n%i==0) {
vv.push_back(i);
if (i!=n/i)
vv.push_back(n/i);
}
lim=n/i;
}
}

factor of 18 = 1,2,9,3,6,18
factorials of 18 = 1*2*3*4*5*6.......*18
why you guys are concentrating on divisors?