查找下一个素数

本文关键字：下一个 查找 | 更新日期: 2023-09-27 18:03:08

我正试图在用户输入的数字之后找到下一个素数。

这是我迄今为止的代码：

public int Calculation(int number)
{
    //set the isPrime to false
    bool isPrime = false;
    //do this while isPrime is still false
    do
    {
        //increment the number by 1 each time
        number = number + 1;
        int squaredNumber = (int)Math.Sqrt(number);
        //start at 2 and increment by 1 until it gets to the squared number
        for (int i = 2; i <= squaredNumber; i++)
        {
            //how do I check all i's?
            if (number % i != 0)
            {
                isPrime = true;
            }

        }

    } while (isPrime == false);
    //return the prime number
    return number;
}

我知道缺少了一些东西，因为当我第一次给出一个不为0的余数时，它会将该数作为素数返回。问题是，我无法弄清楚逻辑/语法，看那个循环中的每个I是否都不是0作为余数。

查找下一个素数

有更好的方法可以找到素数，但为了与算法保持一致，您要做的是从isPrime = true;开始，然后如果有任何余数为0的i，则将其设置为false。您也可以在该点将break从循环中移除。

因此，一个修订版：

public int Calculation(int number)
{    
    while(true)
    {
        bool isPrime = true;
        //increment the number by 1 each time
        number = number + 1;
        int squaredNumber = (int)Math.Sqrt(number);
        //start at 2 and increment by 1 until it gets to the squared number
        for (int i = 2; i <= squaredNumber; i++)
        {
            //how do I check all i's?
            if (number % i == 0)
            {
                isPrime = false;
                break;
            }
        }
        if(isPrime)
            return number;
    }
}

如果使用BitArray作为Eratosthenes的筛，则不需要循环来测试素数。该索引处的BitArray的值将根据其是否为素数而为true或false。

这样的函数将生成Bitarray:

public static BitArray ESieve(int upperLimit)
{
    int sieveBound = (int)(upperLimit - 1);
    int upperSqrt = (int)Math.Sqrt(sieveBound);
    BitArray PrimeBits = new BitArray(sieveBound + 1, true);
    PrimeBits[0] = false;
    PrimeBits[1] = false;
    for(int j = 4; j <= sieveBound; j += 2)
    {
        PrimeBits[j] = false;
    }
    for(int i = 3; i <= upperSqrt; i += 2)
    {
        if(PrimeBits[i])
        {
            int inc = i * 2;
            for(int j = i * i; j <= sieveBound; j += inc)
            {
                PrimeBits[j] = false;                       
            }
        }
    }
    return PrimeBits;
}

声明Bitarray:

BitArray IsPrime = ESieve(1000000);

找到下一个素数是一个简单的问题，即通过比特数组迭代来找到设置为true的下一个：

int FindNextPrime(int number)
{
    number++;
    for(; number < IsPrime.Length; number++)
        //found a prime return that number
        if(IsPrime[number])
            return number;
    //no prime return error code
    return -1;
}

if ((number % i) != 0)
{
    isPrime = true;
}

由于%的运算符优先级低于！=，因此需要将数字%i用括号括起来。我没有测试其余逻辑的正确性，但5的输入正确地返回7作为下一个素数。

相关文章：