約数、素因数

リポジトリ

※自然数の範囲で考えるものとする

確率的素数判定とかは気が向いたら

素数(prime number)

自分自身と1以外の自然数で割り切れない(正の約数をちょうど２つもつ)自然数のこと。

合成数(Composite number)

素数でない2以上の整数(素数の積で表すことができる整数)。

約数(divisor)の列挙

素数判定 (Primality Test) - kanetaiの二次記憶装置の素数判定と同様に実質で割り切れるか確かめればよい(割り切れれば約数)。
ここでは、約数を自然数の範囲で考える。

/**
 * (正の)約数列挙O(√n)
 * @param n
 * @return	nの約数列(sortはされてないよ)
 */
public static ArrayList<Integer> divisor(int n){
	ArrayList<Integer> ret = new ArrayList<Integer>();
	for(int i=1; i*i <= n; i++){
		if( n % i == 0){
			ret.add(i);
			//n=PQ+0→ PもQも約数. ただし、Q=Pは↑で登録済みなので登録しない
			if( i != n/i ) ret.add(n/i); 
		}
	}
	return ret;
}

互いに素(coprime)

互いに素である自然数は1と-1以外に共通の約数を持たない最大公約数が1である自然数は互いに素
したがって素数同士は互いに素。

public static final boolean isCoprime(int a, int b){ return GCD(a,b) == 1; }

素因数(prime factor)

自然数nに対して、nの約数になる素数をnの素因数という。

素因数分解(prime factorization)

自然数nを素数(nの素因数)の積で表すこと方法。1に対する素因数分解を1と定義すると、自然数nの素因数分解は一意に決まる。

/**
 * 素因数分解O(√n)
 * @param n
 * @return	素因数列(昇順)
 */
public static ArrayList<Integer> primeFactor(int n){
	ArrayList<Integer> ret = new ArrayList<Integer>();
	if( n == 1 ){ ret.add(1); return ret; }
	if( n > 1 ){
		for(int i=2; i*i <= n;i++ ){
			while( n % i == 0 ){
				ret.add( i );
				n /= i;
			}
		}
		if( n != 1 ) ret.add( n );
	}
	return ret;
}