通过限制迭代次数来确定一个数字是否为素数——c#

public static bool Isprime(long i)
    {
        if (i == 1)
        {
            return false;
        }
        else if (i < 4)
        {
            return true;
        }
        else if (i % 2 == 0)
        {
            return false;
        }
        else if (i < 9)
        {
            return true;
        }
        else if (i % 3 == 0)
        {
            return false;
        }

else
        {
            double r = Math.Floor(Math.Sqrt(i));
            int f = 5;
            while (f <= r)
            {
                if (i % f == 0) { return false; }
                if (i % (f + 2) == 0) { return false; }
                f = f + 6;
            }
            return true;
        }  
    }

因为每个素数(除了2和3)都是6k +/- 1的形式其他的数不能都是质数，因为它们能被2或3整除此外，对您的方法进行一些修改:

public static bool Isprime(long i)
{
    if (i < 2)
    {
        return false;
    }
    else if (i < 4)
    {
        return true;
    }
    else if ((i & 1) == 0)
    {
        return false;
    }
    else if (i < 9)
    {
        return true;
    }
    else if (i % 3 == 0)
    {
        return false;
    }
    else
    {
        double r = Math.Floor(Math.Sqrt(i));
        int f = 5;
        while (f <= r)
        {
            if (i % f == 0) { return false; }
            if (i % (f + 2) == 0) { return false; }
            f = f + 6;
        }
        return true;
    }  
}

• 您没有检查负数
• 检查一个数字是否为偶数，(i &1) == 0效率更高。不幸的是，i % 3
没有这样的技巧。

虽然一个好的答案已经被接受，并且我之前已经提供了另一个答案，但我为ulong提供了一个新方法，该方法所做的事情略有不同，这可能有助于解释为什么6很重要。这使用for循环而不是while。

UPDATE:我用一个并行线程运行的版本扩展了这个答案。查看这个CodeReview链接获取并行版本。

编辑:添加快速消除许多复合材料

public static bool IsPrime6(ulong number)
{
    // Get the quick checks out of the way.
    if (number < 2) { return false; }
    // Dispense with multiples of 2 and 3.
    if (number % 2 == 0) { return (number == 2); }
    if (number % 3 == 0) { return (number == 3); }
    // Another quick check to eliminate known composites.
    // http://programmers.stackexchange.com/questions/120934/best-and-most-used-algorithm-for-finding-the-primality-of-given-positive-number/120963#120963
    if (!( ((number - 1) % 6 == 0) || ((number + 1) % 6 == 0)) )
    {
        return false;
    }
    // Quick checks are over.  Number is at least POSSIBLY prime.
    // Must iterate to determine the absolute answer.
    // We loop over 1/6 of the required possible factors to check,
    // but since we check twice in each iteration, we are actually
    // checking 1/3 of the possible divisors.  This is an improvement
    // over the typical naive test of odds only which tests 1/2
    // of the factors.
    // Though the whole number portion of the square root of ulong.MaxValue
    // would fit in a uint, there is better performance inside the loop
    // if we don't need to implicitly cast over and over a few million times.
    ulong root = (ulong)(uint)Math.Sqrt(number);
    // Corner Case: Math.Sqrt error for really HUGE ulong.
    if (root == 0) root = (ulong)uint.MaxValue;
    // Start at 5, which is (6k-1) where k=1.
    // Increment the loop by 6, which is same as incrementing k by 1.
    for (ulong factor = 5; factor <= root; factor += 6)
    {
        // Check (6k-1)
        if (number % factor == 0) { return false; }
        // Check (6k+1)
        if (number % (factor + 2UL) == 0) { return false; }
    }
    return true;
}

这是基于数学定理，即所有> 3的质数都可以表示为(6k+/-1)。但这并不意味着(6k+/1)形式的每个数都是素数。

正确的反面应该是，如果你有一个数字不被表示为(6k+/-1)，那么这个数字不可能是素数。

为了以后与模算子一起使用，(6k-1)等价于(6(k+1)+5)。

因此，我们的目的是在5处开始循环，即(6k-1)第一次出现k=1时，在循环内检查(6k-1)和(6k+1)，然后在循环的另一次迭代中增加6。

简而言之，对前一个因子加6的迭代与对k加1的迭代相同。

丑陋的显式强制转换的解释

在进一步的测试表明，对于这个算法，它们几乎没有什么区别后，我去掉了UL指示器。

测试

要运行一些测试，您可以尝试:

const long  Largest63bitPrime =  9223372036854775783L;
const ulong Largest64bitPrime = 18446744073709551557UL;

在我的笔记本电脑上，最大的63位素数需要13秒，最大的64位素数需要18秒。令人惊讶的是，上面的版本对(ulong)Largest63bitPrime比使用我的另一个答案的long特定版本(使用while)快1.5秒。

快速消除许多复合材料

基于对OP本身的评论，我添加了一个新的检查。很难找到最坏的情况，或者最节省时间的情况。我对Largest64bitPrime + 6进行了测试。如果没有检查，则为14.2微秒，而有检查时为1.1微秒。但是现在包含了，所以算法被认为是完整的

看@Dennis_E的回答和解释，我给了+1。我有两种不同的看法。这些语句可以执行上亿次隐式强制转换:

double r = Math.Floor(Math.Sqrt(i));
int f = 5;
while (f <= r)

循环条件隐式地将f反复转换为双精度类型。这就模糊了某些性能可能会降低的地方。虽然long.MaxValue平方根的整个数字部分可以放在uint中，但为了提高性能，您最好将每个都保留为long。现在循环内的性能将受到任何隐式强制转换的影响。

public static bool Isprime1(long number)
{
    // Get the quick checks out of the way.
    if (number < 2) { return false; }
    // 2 and 3 are prime.
    if (number < 4) { return true; }
    // besides 2, any other even number, i.e. any other multiple of 2, is not prime.
    if ((number % 2) == 0) { return false; }
    // 5 and 7 are also prime.
    if (number < 9) { return true; }
    // multiples of 3 are not prime.
    if (number % 3 == 0) { return false; }
    // Quick checks are over.  Must iterate to find the answer.
    // Though the whole number portion of the square root of long.MaxValue
    // would fit in a uint, there is better performance inside the loop
    // if we don't need to implicitly cast over and over a few million times.
    long root = (long)Math.Sqrt(number);
    long factor = 5;
    while (factor <= root)
    {
        if (number % factor == 0L) { return false; }
        if (number % (factor + 2L) == 0L) { return false; }
        factor = factor + 6L;
    }
    return true;
}

以上都扩展了@Dennis_E的答案。另一种变体是:

public static bool Isprime2(long number)
{
    // Get the quick checks out of the way.
    if (number < 2) { return false; }
    // 2, 3, 5, & 7 are prime.
    if ((new long[] { 2L, 3L, 5L, 7L }).Contains(number)) { return true; }
    // any other multiples of 2 are not prime.
    if ((number % 2) == 0) { return false; }
    // any other multiples of 3 are not prime.
    if (number % 3 == 0) { return false; }
    // Quick checks are over.  Must iterate to find the answer.
    // Though the whole number portion of the square root of long.MaxValue
    // would fit in a uint, there is better performance inside the loop
    // if we don't need to implicitly cast over and over a few million times.
    long root = (long)Math.Sqrt(number);
    long factor = 5;
    while (factor <= root)
    {
        if (number % factor == 0L) { return false; }
        if (number % (factor + 2L) == 0L) { return false; }
        factor = factor + 6L;
    }
    return true;
}

public class Prime {
public static void main(String[] args) {
    Scanner get=new Scanner(System.in);
    int n;
    System.out.println("Enter a number to find its primality");
    n=get.nextInt();
    System.out.println(n+" isPRime? "+isPrime(Math.ceil(Math.sqrt(n)),n));
}
private static boolean isPrime(double n,int k){
  boolean isPrim=true;
  int p=(int)n;
  for(int i=2;i<=p;i++){
      boolean iprime=false;
      for(int j=2;j<i/2;j++){
          if(i%j==0){
              iprime=true;
              break;
          }              
      }
      if(!iprime && k>i){
          if(k%i==0){
              isPrim=false;
              return isPrim;
            }
         }
       }
  return isPrim;
}
}