2

我正在制作一个素数查找器，它将找到用户输入的给定数字的素数。我现在所拥有的似乎要么错过素数，要么将非素数添加到 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;
}
}
4

6 回答 6

0

首先，而不是

    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 两次。

任何比这更复杂的事情都是不必要的 - 你会尝试每个 j 直到它不能再分成 n ，并且你总是会在由这些素数形成的复合之前尝试素数，所以你知道你最终只会得到素数.

于 2013-03-18T01:08:47.233 回答
0

我会给你一些伪代码，用于简单实现（效率不高）的算法：

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
于 2013-03-18T01:24:29.320 回答
0

一个使代码更简单的建议。在你的 primeFactors 方法中，首先找出它是一个因素，我相信你已经在做，然后调用另一个方法来确定这是否是一个素数。如果那是主要添加到列表中。

于 2013-03-18T01:13:38.240 回答
0
  1. 您的变量名称不一致。factors特别糟糕，因为它只是一个单一因素的猜测。guess改为调用它。
  2. 你用factors,primes和做的算术dup也很奇怪。你为什么要添加到dupor primes？尝试成为您自己的计算机，并为数字 12 执行您的算法；你会发现你根本没有正确的算法。
  3. factors您已经通过在末尾增加来排除重复因素的可能性。
于 2013-03-18T01:45:37.120 回答
0

好的，您的代码存在一些问题：

  1. j、x、j 和 n，命名不佳的变量使调试工作变得困难。
  2. 您的电话在哪里，System.out.println()以便您可以看到代码中发生了什么？
  3. n 的平方根将是停止寻找直到 n 的素数的更优点。

我可以建议你看看这个：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes寻找素数的快速方法。

于 2013-03-18T01:12:26.670 回答
0

您在这里所做的数学和逻辑非常奇怪，我不太了解正在发生的事情。

为此，我会投票 +1 以简化代码。这可以通过两种简单的方法来完成。第一种方法将找到一个数字的因子并通过质数检查器运行它们。如果它们是一个因素并通过了质数检查，它们就会被添加到数组中。

奖励点：通过仅搜索因子检查器和素数检查器的下半部分来提高算法的速度。逻辑是任何超过半数的值都不能成为该数字的一个因素。

更多的速度加分，增加 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;
    }
}
于 2013-03-18T02:06:17.153 回答