java - 返回质数数组

Question

我需要一种方法来返回数组中的素数。

所以如果给出:primeArray(5)

应该返回这样的数组:(2, 3, 5)

出于某种原因，这似乎对我不起作用:

public static int[] primeArray(int numFind)
{
    //determines the size of the array returned
    int primeTotal = 0;

    //loop to find total prime numbers
    for (int j = 1; j <= numFind; j ++)
    {
        if (isPrime(j))
        primeTotal +=1;
    }

    //declare array to be returned
    int[] numA = new int[primeTotal];

    //current index of prime number
    int iP = 0;

    //loop to add prime elements to array
    for (int x = 1; x <= numFind; x ++)
    {
        if (isPrime(x))
        {
            numA[iP]=x;
            iP++;    // <--- THIS IS CAUSING ME PROBLEMS
        }

    }

    return numA;
}

public static boolean isPrime(int n)
{
    for (int i = 2; i < n; i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

这是我用来测试我的代码的:

    int[] num = primeArray(11);

    System.out.println(num[0]);
    System.out.println(num[1]);

但是对于输出我得到这个:

1 
2

但是如果我注释掉 iP++；比 if 语句最终决定仅在将质数作为参数传递给 isPrime(j) 时才执行，但随后 if 破坏了 primeArray 方法的全部目的，因为我需要 primeArray 方法返回质数数组。

Answer 1

你的 isPrime()方法有误。您需要返回 false , 对于 number < 2 .此外，您不需要迭代到 n，只需迭代到 n/2 或更好的 sqrt(n) .

将其更改为:

public static boolean isPrime(int n) {

    if (n < 2) return false;

    int maxIteration = Math.ceil(Math.sqrt(n));

    for (int i = 2; i < maxIteration; i++) {
        if(n % i == 0)
            return false;
    }

    return true;
}

现在，考虑到您的实际问题(请注意，您的方法很好。如果您更改了 isPrime() 方法，它会返回正确的结果)，但您可以通过使用避免迭代两次一个 ArrayList 而不是数组:

List<Integer> primes = new ArrayList<Integer>();

//loop to find total prime numbers
for (int j = 1; j <= numFind; j ++)
{
    if (isPrime(j))
        primes.add(j);
}

然后你可以只返回素数，并将方法的返回类型更改为List<Integer>而不是 int[] .

public static List<Integer> primeNumberList(int numFind)

如果你真的想返回一个 int[] , 然后你需要做一些工作来转换 ArrayList到int大批。我把这个任务留给你。只在 SO 上搜索这个，你会得到太多帖子。

---

另外，如果你要生成所有素数直到一个非常大的数，那么你应该看看 Sieve of Eratosthenes