5

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

所以如果给定： 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 方法返回一个素数数组。

4

8 回答 8

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()方法），但你可以避免使用 an而不是array迭代两次：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);
}

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

public static List<Integer> primeNumberList(int numFind)

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

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

于 2013-07-31T06:24:41.487 回答
0

在您的isPrime()方法中，在末尾添加此语句

if(n < 2) return false;

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

我能想到的另一个建议是，如果您希望您的限制很小，您可以对一些数字使用静态表。

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

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

于 2013-07-31T06:23:57.177 回答
0

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

只需替换您的输出

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

您的代码工作正常。

于 2013-07-31T06:22:48.360 回答
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;
  }
于 2013-12-31T13:44:53.230 回答
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;

}
于 2013-12-31T15:52:27.643 回答
0

您可以通过使用 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;
}
于 2019-08-12T06:32:46.840 回答
0

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

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(...)用来检查了；）

于 2018-08-05T21:11:38.197 回答
0 
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;
}

}

于 2019-08-12T05:26:44.847 回答