どのようにして質量因数を分解しますか?

1932 ワード

タイトルの説明:
正の整数を質量係数に分解します.例えば、90と入力し、90 = 2 * 3 * 3 * 5を印刷します.
概念整理:
質量数とは?
質量数(Prime Number)とは、1より大きい自然数のうち、1および によってのみ除去される自然数を指す.
どのようにして整除を判断しますか?
除数nおよび被除数Nが与えられ、N / nの剰余がゼロである場合、Nnによって除算されることができると称される.プログラミングでは、 を使用して問題を解決することができる.
分解質因数とは何ですか.
一つの合数をいくつかの質量数に乗算する形式に書くことを分解質量因数と呼ぶ.
構想分析:
  • 素数の定義に基づいて、自然数が素数であるか否かを判断するアルゴリズムを実現する.
  • 1~Nのすべての質量数を探し出す.
  • サイクルは、N1~Nの質量数で除去されるか否かを判断し、除去されることができれば、その質量数はNの質量因数である.
  • は、第3ステップの整除後の結果を取得し、整除の結果も素数になるまで、第2、3の2ステップを繰り返し実行する.

  • コード実装:
  • は、1つの数が素数
  • であるか否かを判断する.
    /**
     *          
     *      n   1 n  ,      , :
     *      n   1~n        ,      。
     */
    public boolean isPrimeNumber(int n) {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
  • 再帰分解素因数
  • public void factoringNumber(int n) {
        if (isPrimeNumber(n)) {
            System.out.print(n); //   n   ,       
            return;
        }
        for (int i = 2; i < n; i++) {
            if (isPrimeNumber(i)) { // i     
                if (n % i == 0) { // n    i  
                    System.out.print(i + " * ");
                    int result = n / i; //       
                    factoringNumber(result); //        
                    break; //   :             
                }
            }
        }
    }
    
  • 分解素因数試験
  • factoringNumber(1001); // 7 * 11 * 13
    

    まとめ:
    問題を解決するには、まず問題の各基本概念をクリアすることです.基本概念がはっきりしていなければ、正確に考えるのは難しい.
    例えば本題では,まず素数,整除,残数,分解素因数などの概念を明らかにする.基本概念を深く理解した後、問題を解決するのは虎に翼を添えるようになった.
    テーマには注意すべき点があります.素因数を見つけた後、ループを終了しなければなりません.そうしないと、ループが実行されます.
    コード実行結果が予想された結果と一致しない場合、冷静に分析するには、コードロジック(Debug)に従って脳で1回実行すればよい.