java - 素数ファインダーは独自の心を持っていますか？

Question

私は素数ファインダーを作成しています。これは、ユーザーが入力した特定の数の素数を検索します。私が今持っているものは、素数を見逃しているか、ArrayListに非素数を追加しているようです。私のコードは私には論理的であるように思われ、なぜこれが起こっているのかについて私は混乱しています。誰かが私が間違っていることを教えてもらえますか？それとも、これを行うためのより簡単な方法（私は過度に複雑になっているように感じます）？エラーの例としては、次のようなものがあります。21と入力すると、プライムとして3つだけが表示されます。11000と入力すると、25と55が表示されます（明らかに素数ではありません）。前もって感謝します！

import java.util.*;

public class PrimeFactors {

public static void main(String args[]) {
    long num;
    Scanner in = new Scanner(System.in);

    System.out.println("\n\n\nThis program finds the prime factors of a given number.\n");
    System.out.print("Please enter the number: ");
    num = in.nextLong();
    System.out.println("\nThe prime factors are: " + primeFactor(num) + "\n");
}

public static ArrayList<Long> primeFactor(long n) {
    long output = 0;
    long guess = 2;
    ArrayList<Long> primeFactors = new ArrayList<Long>();

    while (guess <= n) {
        long primes = 0;
        long i = 2;
        long x = 0;
        long rt = 1;
        long duplicate = 0;

        output = n % guess;

        // Finds the sqrt.          
        while (x <= n) {
            x = rt * rt;
            rt++;
        }

        // Finds odd factors.    
        if ((output == 0) && (guess % 2 != 0)) {
            // This divides the odd factor by an incrementing number that is not 1 or the number itself.
            while (i < rt) {
                primes = primes + (guess % i);
                // If the sum of the remainders to the division is not 0, then the number is prime.
                // I used duplicate to make sure it didn't just go through once and count as prime.
                if (primes != 0){
                    // There were duplicates, so I added them for the division later.
                    duplicate = duplicate + guess;
                    // This was used to wait for the while loop to finish, then find if the amount of times the guess went through was equal to its value - 1 and another 1 for the final number (primes are only divisible by one and itself).
                    if (i == (factors - 1)) {
                        if ((duplicate / guess) == (guess- 2)) {
                            primeFactors.add(guess);
                        }
                    }
                }
                i++;
            }
        }
        guess++;
    }
    return primeFactors;
}
}

Answer 1

あなたがここで行っている数学と論理は非常に奇妙であり、私は何が起こっているのかを完全には追跡していません。

そのために、コードを単純化するために+1に投票します。これは、2つの簡単な方法で実行できます。最初の方法では、数値の因子を見つけて、素数チェッカーを実行します。それらが因子であり、素数チェックに合格した場合、それらは配列に追加されます。

ボーナスポイント：ファクターチェッカーとプライムチェッカーのそれぞれの下半分のみを検索することにより、アルゴリズムの速度を上げます。論理は、半分の数を超える値はその数の要因にはなり得ないということです。

速度のボーナスポイントが増え、2の倍数をすべてスキップして、2ずつ増加します。これは、自動的に素数ではないためです。幸運を！

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

/***************************************************
 *
 * @file: PrimeFactors.java
 * @date: Mar 17, 2013
 * @author: AaronW
 */

/**
 *
 * @author AaronW
 */
public class PrimeFactors {

    public PrimeFactors() {
    }

    /**
     *
     * @param args
     */
    public static void main(String[] args) {

        long num;
        Scanner in = new Scanner(System.in);

        System.out.println("\n\n\nThis program finds the prime factors of a given number.\n");
        System.out.print("Please enter the number: ");
        num = in.nextInt();
        System.out.println("\nThe factors are: " + findFactors((double)num) + "\n");
    }

    public static ArrayList<Integer> findFactors(Double num) {
        ArrayList<Integer> factors = new ArrayList<Integer>();

        for (int x = 1; x <= num; x++) {
            System.out.println("Testing " + num + " % " + x + " = " + num % x);
            // First, let's see if a number is factor of your target number
            if (num % x == 0) {
                System.out.println(x + " is a factor");
                // Now that we know it's a factor, let's test to see if it's prime
                if (isPrime(x)) {
                    // If it's prime, add it to the ArrayList
                    System.out.println("And " + x + " is prime.");
                    factors.add(x);
                } else {
                    System.out.println("But " + x + " is not prime.");
                }
            } else {
                System.out.println(x + " is not a factor");
            }
        }

        return factors;
    }

    public static boolean isPrime(double num) {
        // Let's start by assuming everything is prime and try to prove that false
        // If we fall through the loop without proving it false, we have a prime
        boolean prime = true;

        for (int x = 2; x < num; x++) {
            // if our target number can be divided by any number between 1 and itself, it is not prime
            if (num % x == 0) {
                prime = false;
            }
        }

        return prime;
    }
}

Answer 2

まず、代わりに

    long x = 0;
    long z = 1;

    while (x <= n) {
        x = z * z;
        z++;
    }

    while (j < z) {

あなたはこれを行うことができます

    z = (int) Math.Sqrt(n)
    while (j <= z) {

次に、jごとに、nを余りなしで除算するかどうかを確認します。

nを余りなしで除算する場合は、nをjで除算し、jを素因数に加算します。次に、jをインクリメントする代わりに、同じjを再試行します。たとえば、9の場合、その因数に対して3を2回実行します。

それよりも複雑なことは不要です。nに分割できなくなるまで各jを試し、それらの素数で構成される複合体の前に常に素数を試すので、素因数だけで終わることがわかります。 。

Answer 3

OK、コードにはいくつか問題があります。

1. j、x、j、nの名前が不適切な変数は、デバッグに苦労します。
2. System.out.println()コードで何が起こっているかを確認できるように、呼び出しはどこにありますか？
3. nの平方根は、nまでの素数の検索を停止するためのより最適なポイントになります。

素数をすばやく見つける方法については、 http ：//en.wikipedia.org/wiki/Sieve_of_Eratosthenesをご覧ください。

Answer 4

コードを単純化するための1つの提案。PrimeFactorsメソッドでは、最初にそれが要因であることがわかります。これはすでに実行していると思います。次に、別のメソッドを呼び出して、これがプライムであるかどうかを判断します。それが素数である場合は、リストに追加してください。

Answer 5

実装が簡単な（効率的ではない）アルゴリズムの擬似コードをいくつか紹介します。

the value to factorize is N
keep going until N is equal to one
  start at 2 and find lowest number X that divides N evenly
  X is one factor
  N/X is your new N to factor

Answer 6

1. 変数名に一貫性がありません。factorsそれは単一の要因の推測にすぎないので、特に悪いです。代わりにそれを呼び出しguessます。
2. factors、、primesで行う算術dupも奇妙です。なぜ追加するのですdupかprimes？自分のコンピューターになって、12番のアルゴリズムを実行してみてください。正しいアルゴリズムがまったくないことがわかります。
3. 最後にインクリメントfactorsすることで、繰り返される要因の可能性を排除しました。