java 返回一个素数数组

return an array of prime numbers

提问by user2636774

I need a method to return prime numbers in an array.

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

So if given: primeArray(5)

所以如果给定： primeArray(5)

than an array like so should be returned: (2, 3, 5)

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

For some reason this doesn't seem to work for me:

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

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;
}

This is what I'm using to test my code:

这是我用来测试我的代码的内容：

    int[] num = primeArray(11);

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

But for output I'm getting this:

但是对于输出，我得到了这个：

1 
2

If however I comment out the iP++; than the if statement finally decides to execute ONLY when prime numbers are passed as a parameter in: isPrime(j) but then if defeats the whole purpose of the primeArray method because I need the primeArray method to return an array of prime numbers.

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

回答by Rohit Jain

Your isPrime()method is faulty. You need to return false, for number < 2. Also, you don't need to iterate till n, just iterate till n / 2or even better sqrt(n).

你的isPrime()方法有问题。你需要返回false，因为number < 2。此外，您不需要迭代到n，只需迭代到n / 2甚至更好sqrt(n)。

Change it to:

将其更改为：

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;
}

Now, given your real problem (Note that your method is just fine. It would return you correct result, given you changed your isPrime()method), but you can avoid iterating twiceby using an ArrayListinstead of array:

现在，考虑到您的实际问题（请注意，您的方法很好。如果您更改了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);
}

And then you can just return primes, and change the return type of method to List<Integer>instead of int[].

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

public static List<Integer> primeNumberList(int numFind)

If you really want to return an int[], then you need to do some work converting the ArrayListto an intarray. I leave this task to you. Just search for this on SO only, you will get too many posts.

如果你真的想返回一个int[]，那么你需要做一些将 转换ArrayList为int数组的工作。我把这个任务交给你。只在 SO 上搜索这个，你会得到太多的帖子。

---

---

Also, if you are going to generate all prime numbers till a very large number, then you should take a look at Sieve of Eratosthenes

另外，如果您要生成所有质数直到一个非常大的数字，那么您应该看看埃拉托色尼筛

回答by Loki

You just do the output for the first to Array-Values...

您只需将第一个输出到 Array-Values...

just replace your output

只需更换您的输出

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

Your code works fine.

你的代码工作正常。

回答by midhunhk

In your isPrime()method, add this one statement at the end

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

if(n < 2) return false;

if(n < 2) return false;

I think in the current way, when 1 is passed you get a true.

我认为以目前的方式，当 1 被传递时，你会得到一个真实的。

Another suggestion that I can think of is you can use a static table for some amount of numbers if you expect your limit to be small.

我能想到的另一个建议是，如果您希望限制很小，则可以使用静态表来存储一定数量的数字。

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

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

So when the limit is smaller than 32 in this example, you don't need to calculate all the prime numbers below it and just loop through this table and return the numbers.

所以当这个例子中的限制小于 32 时，你不需要计算它下面的所有质数，只需循环遍历这个表并返回数字。

回答by Deepsthecoder

I tried to write isPrime(int num) function in a bit different way. The code becomes a bit more lengthy but works. I used a different logic to identify if the number is 1 , because 1 is neither prime nor composite. Code is below.

我尝试以不同的方式编写 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;
  }

回答by Deepsthecoder

this code return all prime numbers less than n

此代码返回所有小于 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;

}

回答by Robert E Fry

There are a few ways to get an array of prime numbers, the easiest computationally is to use a Sieve of Eratosthenes. This iterates over every increasing number, where when the next prime is found, all subsequent multiples of this are marked not prime. Most implementations use a boolean array as below:

有几种方法可以获得素数数组，最简单的计算方法是使用埃拉托色尼筛法。这将迭代每个增加的数字，当找到下一个素数时，所有后续的倍数都被标记为不是素数。大多数实现使用布尔数组，如下所示：

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;
        }
    }
}

This method is good for a quick way to generate an array of primes, but it can get very memory-intensive for large maximum limits.

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

An alternate way of going about this problem is the way you have done it, where you simply add the next prime number when you find it. Your implementation though could become more efficient from the following.

解决这个问题的另一种方法是你的方法，你只需在找到下一个质数时添加它。不过，您的实施可以通过以下方式变得更有效率。

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;
}

Starting with the corrected implementation suggested by Rohit Jain (as above), you may notice you don't have to test every number less than sqrt(p). If pis not divisible by n, then it is not going to be divisible by the multiples of n- such we only need to test every prime number below p. For example; since 7 is not divisible by 2, it's not going to be divisible by 4 either.

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

The problem here is that we now need to find which numbers less than sqrt(p)are prime to test against p. Ah, but no we don't! We can just look into our cached list of known primes we will be later returning in the other method. And while we're caching a list of known primes, we don't need to make a new list in the other method either, we can just return our cache (once generated)! The finished product will look something like this:

这里的问题是我们现在需要找出哪些数小于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;
    }

}

Now you can use Primes.isPrime(...)to check ;)

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

回答by Ajay

public class Demo {
public static void main(String[] args) {
    int result[] = ArrayOfPrimeNumbers(30);
    for (int i = 0; i < result.length; i++) {
        System.out.println("Factor: " + result[i]);
    }
}
public static int[] ArrayOfPrimeNumbers(int n) {
    int countPrimeNumbers = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            countPrimeNumbers++;
        }
    }
    int newArrayofPrime[] = new int[countPrimeNumbers];
    int count = 0;
    while (count < countPrimeNumbers) {
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                newArrayofPrime[count] = i;
                count++;
            }
        }
    }
    return newArrayofPrime;
}
public static boolean isPrime(int n) {
    if (n <= 1)
        return false;

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

    return true;
}

}

}

回答by hafiz031

You can way more optimize it by using Sieve algorithm to find primes. Following implementation can find primes upto (10^9)-1.

您可以通过使用 Sieve 算法查找素数来对其进行更多优化。以下实现可以找到高达 (10^9)-1 的素数。

#include<iostream>//for I/O
#include<vector>//for keeping primes
#include<math.h>//for sqrt()
#define lli long long int
using namespace std;
vector<lli>prime;//using long long int data type for getting result for relatively bigger numbers...you may use int if you are working with smaller numbers.
lli upto;
bool stat[100000001];//Status array to keep track for primes/non-primes (0=prime, 1=non-prime, initially all are 0)
void sieve(lli upto)
{
    lli n=upto;
    stat[0]=stat[1]=1;//Marking 0 and 1 as they are not primes
    for(lli i=4;i<=n;i+=2)//Marking all even numbers as they won't be primes
    {
        stat[i]=1;
    }
    lli sqrtn=sqrt(n);
    //You can check if a number is prime or not just by making sure it is not divisible by any numbers upto it's square-root.
    //The reason of not checking the numbers after that is that if the number is divisible by a number greater than or equal to its square-root,
    //then we surely have already found another number which also divides the number less than or equal to its square root. For example to check if 36 is
    //a prime we can try dividing it with numbers <=sqrt(36) or <=6.We need not go beyond it. Say we need not check with 9 or 12 etc. as we have already checked
    //the divisibility with their conjugates 4 and 3 respectively (as 4*9=36 and 3*12=36) and found that 36 is getting divided, hence non prime.
    for(lli i=3;i<=sqrtn;i+=2)//So continuing this loop upto sqrt(n) and starting from 3 and stepping to only the odd numbers,as we cannot expect an even number to be a prime (except 2)
    {
        if(stat[i]==0)//ith index is still unmarked means it is a prime
        {
            //..so leaving ith index unmarked we are marking all the multiples of i as number i will divide them and they won't be primes.
            //But again we can do some optimizations:
            //(1) The next unmarked number divided by i, greater than i will be i*i. Because numbers less than i*i which is also divided by i are already marked by some numbers<i. An example will make it clear:
            //    Say for 5 we will start marking from 5*5=25, although 15 is divided by 5 but we need not mark it again as it is already marked by 3 (as 3 also divides 15) when we worked with 3.
            //(2) We are advancing our checking 2*i times as we are now searching for primes in odd numbers only, so we are skipping the marking for even numbers (say for 3, starting check from 3*3=9, we will next check 9+2*i=9+2*3=15 (we skipped checking 12 as it is even and we have already marked all even numbers initially (except 2) for being non-primes).
            for(lli j=i*i;j<=n;j+=2*i)
            {
                stat[j]=1;//so marking the indexes corresponding to numbers which are divisible by j as they are non-primes.
            }
        }
    }
    for(lli i=2;i<=n;i++)
    {
        if(stat[i]==0)//Finally finding which are still unmarked as the are not divisible by any number (except divisible by 1 and the number itself as prime number's definition) and the numbers corresponding to these indexes are primes.
        {
            prime.push_back(i);//storing primes, as index i is unmarked so i is a prime.
        }
    }
}
int main()
{
    cout<<"Enter upto which number you want to look for primes: ";
    cin>>upto;
    sieve(upto);
    for(int i=0,z=prime.size();i<z;i++)//printing
    {
        cout<<prime[i]<<" ";
    }
    cout<<endl;
}