Tag Archive for 'divisor'

What Does Evenly Divisible Mean?

Published on August 4, 2010 in Problems. 0 Comments

I thought it meant the quotient should be even!!

But no! It means dividing a group of objects into subgroups of even size, i.e; same size.  Simply put, A is evenly divisible by B if it leaves no remainder.

Popularity: 5% [?]

Sum Of Divisors

Published on January 20, 2010 in Problems. 0 Comments

Let n be an integer factorized as following:

n = {p_1}^{e_1} \times {p_2}^{e_2} \times \ldots \times {p_k}^{e_k}

The sum of divisors of n is:

\sigma(n) = a_1 \times a_2 \times \ldots \times a_k

where,

a_k = \frac{{p_k}^{e_k + 1} - 1}{p_k - 1} = {p_k}^{e_k} \times \ldots \times {p_k}^{2} \times {p_k}^{1}

In the simpler case of n = p^e, the sum is

\sigma(n) = p^e \times \ldots \times p^2 \times p

This I learned from the article written by Hisanori Mishima found here. The idea translates into a nice little loop to find the sum of divisors. The Java implementation of it has been done by me and is thus:

package pba.common.number;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class PrimeNumber {
	private List<Integer> m_primeNumbers;

	/**
	 * @param sizeOfSieve The upper bound to the determination of prime numbers.
	 */
	public PrimeNumber(int sizeOfSieve) {
		m_primeNumbers = new ArrayList<Integer>();
		sieveOfEratosthenes(sizeOfSieve);
	}

	/**
	 * @param number The number whose sum of divisors is required
	 * @return The sum of divisors of the given number
	 */
	public int getSumOfDivisors(int number) {
		int sum = 1;
		while (number > 1) {
			int temp = 1;
			int primeFactor = getSmallestPrimeFactor(number);
			while (number % primeFactor == 0) {
				temp = temp * primeFactor + 1;
				number /= primeFactor;
			}
			sum *= temp;
		}

		return sum;
	}

	/**
	 * @param number The number whose smallest prime factor is required
	 * @return The smallest rpime factor for the given number
	 */
	public int getSmallestPrimeFactor(int number) {
		for (int prime : m_primeNumbers)
			if (number % prime == 0)
				return prime;

		return Integer.MIN_VALUE;
	}
}

Note that the list of prime numbers can be quickly found by using the Sieve of Eratosthenes.

Popularity: 12% [?]