アルゴリズム（階乗、素数判定、エラトステネスの篩、約数、素因数分解）

階乗計算プログラム

Ex.java

import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Long ans = func(n);
        System.out.println(ans);
    }
    //再帰関数
    public static Long func(int n){
        if(n==0)return 1;
        return n*func(n-1);
    }
}

素数判定プログラム

ex.java

import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean ans = isPrime(n);
        System.out.println(ans);
    }
    public static boolean isPrime(int n){
        for(int i=2;i*i<=n;i++){
            if(n%i==0)return false;
        }
        return true;
    }
}

• 素数とは、1と自分自身以外では割り切れない数。調べる範囲は2から√Nまでが最も効率いい
• √Nについて、

ex.java

for (int i = 2; i <= Math.sqrt(N); i++)

→理論上間違いではないが、Math.sqrt は double,浮動小数点誤差のリスク,毎ループで平方根計算（遅い）などの問題がある

i ≤ √N

↓　両辺を二乗すると（i ≥ 0 なので問題なし）

i² ≤ N

↓　これをそのままコード化すると

i * i <= N

• N がiで割り切れる場合は、素数ではないので false を返す
• すべてのiに対してN%i≠0である場合、素数と判定して true を返す

エラトステネスの篩

自然数だけを並べた自然数列（progression of natural numbers）から合成数（約数をもつ自然数）をふるい落として素数（1と自身以外に約数をもたない2以上の自然数）だけを残す手順

素数出力プログラム

ex.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("nまでの素数を出力します。n = ");
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        //篩
        //isPrime[i] が true なら、i はまだ素数の候補
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // iの倍数をすべて素数じゃないとマーク
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        //出力
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        System.out.println("素数: " + primes);
    }
}

• i が素数なら、その**倍数（2i, 3i, 4i…）**は必ず素数ではない
• したがって、それらを false にして「ふるい落とす」
• 内側ループを j = i * i から始めるのは、i より小さい数の倍数（例：2 * i）はすでに他の素数で除外されているから
• 外側のループを i * i <= n までにしているのも同じ理由で、それ以上では新しいふるい落としは発生しないから
• O(n log log n) という非常に高速な素数判定処理となる
  例
  n=30：各素数pの倍数（2p, 3p, 4p...）は素数ではないから消す

i	倍数として消す
2	4, 6, 8, 10, 12, …, 30
3	6, 9, 12, 15, …, 30
5	10, 15, 20, 25, 30
…	…

たとえば今、i = 5 のときに倍数を消そうとする
⇒5×2=10, 5×3=15, 5×4=20, 5×5=25, 5×6=30 ...
⇒でもよく見ると、
10, 15, 20 はすでに前のステップで別の小さい数（2×5や3×5）の倍数として消されている

• 篩がどう動くかの例（i = 2、n = 20）
• for (int i = 2; i * i <= 20; i++) →√20は約4.47なのでi=2,3,4

i=2のとき
if (isPrime[2]) // true
for (int j = i * i; j <= 20; j += i)
開始：
j = 2 * 2 = 4
j=20になるまでループが続く
isPrime[4]=false
↓
j+=iよりj=4+2=6
↓
isPrime[6]=false
...

素数カウントプログラム

Ex.java

import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] isPrime = new boolean[n+1];
        for(int i=2;i<=n;i++){
            isPrime[i] = true;
        }
        //篩
        for(int i=2;i*i<=n;i++){
            if(isPrime[i]){
                for(int j=i*i;j<=n;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        //素数カウント
        int count =0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) count++;
        }
        //出力
        System.out.println(count);
    }
}

約数列挙

約数の列挙も素数判定と同じような方法で可能

divisor.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();

        for (long i = 1; i * i <= N; i++) {
            if (N % i != 0) continue; // 余りが0でなければ i は約数ではない
            System.out.println(i);
            if (i != N / i) { // ペアの約数（N/i）が重複しないように出力
                System.out.println(N / i);
            }
        }

        sc.close();
    }
}

• 割り切れる→ペアの約数も一緒に出力

素因数分解

入力値を素因数分解して列挙

factorization.java

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		// 素因数分解・出力（空白区切りの場合）
        //flag は、空白を入れるかどうかの判定に使う
		boolean flag = false;
		for (long i = 2; i * i <= N; i++) {
			while (N % i == 0) {
				if (flag == true) System.out.print(" ");
				flag = true;
				N /= i;
				System.out.print(i);
			}
		}
        //一番最後の素因数
		if (N >= 2) {
			if (flag == true) System.out.print(" ");
			flag = true;
			System.out.print(N);
		}
		System.out.println();
	}
}