読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

約数、素因数

Algorithm

リポジトリ

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

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

素数(prime number)

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

合成数(Composite number)

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

約数(divisor)の列挙

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

/**
 * (正の)約数列挙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以外に共通の約数を持たない \Leftrightarrow最大公約数が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;
}