返回一个素数数组

问题描述 投票:5回答:6

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

所以如果给出: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)但是如果违反了primeArray方法的全部目的,因为我需要primeArray方法来返回素数数组。

java
6个回答
10
投票

你的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


0
投票

你只需要输出第一个到Array-Values的输出......

只需替换你的输出

for(int i = 0; i < num.length; i++)
{
    System.out.println(num[i]);
}

你的代码运行正常。


0
投票

在你的isPrime()方法中,最后添加这一个语句

if(n < 2) return false;

我认为按照目前的方式,当1通过时,你会得到一个真实的。

我能想到的另一个建议是,如果你希望你的限制很小,你可以使用一个静态表来获取一定数量的数字。

static int[] PRIME_TABLE = {2,3,5,7,11,13,17,19,23,29,31};

因此,当此示例中的限制小于32时,您不需要计算其下面的所有素数,只需遍历此表并返回数字。


0
投票

我尝试以不同的方式编写isPrime(int num)函数。代码变得有点冗长但有效。我使用不同的逻辑来识别数字是否为1,因为1既不是素数也不是复合数。代码如下。

   static int count=0;
   static boolean flag;
public static boolean isPrime(int num){

    for(int i = 1; i<=num/2 ; i++){

        if(num%i ==0){

            count++;

            if(count >=2){

                flag = false;    
            }
            else{
                  if( num/1==1){
                      flag = false;
                  }
                  else{
                      flag = true;
                  }

            }

         }
    }
        return flag;
  }

0
投票

此代码返回小于n的所有素数

public ArrayList<Integer> allPrimesLessThanN( int n) {

    int sqrtN = (int)Math.sqrt(n);
    int [] numberList = new int[n];
    ArrayList<Integer> primeList = new ArrayList<>();

    for( int i = 0; i < n ; i++) 
    {
        numberList[i] = i+1;
    }

    int k = 2;
    while( k <= sqrtN)
    {
        if(numberList[k+1] != 0)
        {
            for( int j = k+1; j < n; j++)
            {
                if( numberList[j] % k == 0)
                {
                    numberList[j] = 0;
                }
            }
        }

        k++;
    }

    for( int i = 1; i < n; i++)
    {
        if(numberList[i] != 0)
            primeList.add(numberList[i]);
    }

    return primeList;

}

0
投票

有几种方法可以获得素数数组,最简单的计算方法是使用Eratosthenes筛选。这将迭代每个递增的数字,其中当找到下一个素数时,其后续的所有倍数都标记为非素数。大多数实现使用如下的布尔数组:

boolean[] numbers = new boolean[max];
// At first, assume every number is prime
for (int i = 0; i < max; i++) 
    numbers[i] = true; 
// Zero and one are not primes
numbers[0] = number[1] = false;

// Begin iteration from 2, the smallest prime
for (int i = 2; i < max; i++) {
    // if i is prime, all multiples of i are not prime
    if (numbers[i]) {
        for (int j = i * 2; j < max; j += i) {
            numbers[j] = false;
        }
    }
}

此方法适用于快速生成素数数组的方法,但对于较大的最大限制,它可能会占用大量内存。

解决这个问题的另一种方法是你已经完成它的方式,你只需在找到它时添加下一个素数。您可以通过以下方式提高实施效率。

boolean isPrime(double p) {
    if (p < 2) return false;
    for (int i = 2; i <= Math.sqrt(p); i++) if (p % i == 0) return false;
    return true;
}

从Rohit Jain建议的纠正实施开始(如上所述),您可能会注意到您不必测试每个小于sqrt(p)的数字。如果p不能被n整除,那么它就不会被n的倍数整除 - 这样我们只需要测试p以下的每个素数。例如;因为7不能被2整除,所以它也不会被4整除。

这里的问题是我们现在需要找到小于sqrt(p)的数字来测试p。啊,但不,我们不!我们可以查看我们稍后将在其他方法中返回的已知素数的缓存列表。虽然我们正在缓存一个已知素数列表,但我们也不需要在另一个方法中创建一个新列表,我们可以只返回我们的缓存(一旦生成)!成品看起来像这样:

class Primes {

    private static final List<Double> known_primes = new ArrayList<Double>(Collections.singletonList(2d));

    public static boolean isPrime(double p) {
        if (p < 2) return false; // 2 already in our cache
        if (known_primes.contains(p)) return true; // found prime in cache
        for (double i = 3; i <= Math.sqrt(p); i += 2) { // only check odd numbers
            if (!isPrime(i)) continue; // only check primes
            if (p % i == 0) return false; // p is divisible by i, so not prime
        }
        // checked all possible divisors, so p must be prime - cache and sort it!
        known_primes.add(p);
        Collections.sort(known_primes);
        return true;
    }

}

现在你可以使用Primes.isPrime(...)来检查;)

© www.soinside.com 2019 - 2024. All rights reserved.