C# C - 判断一个数是否为素数

Question

提问by Jimmy

I am trying to come up with a method that takes an integer and returns a boolean to say if the number is prime or not and I don't know much C; would anyone care to give me some pointers?

我正在尝试提出一种方法，该方法接受一个整数并返回一个布尔值来说明该数字是否为素数，并且我对 C 了解不多；有人愿意给我一些指点吗？

Basically, I would do this in C# like this:

基本上，我会在 C# 中这样做：

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

Answer 1

采纳答案by Stephen Canon

OK, so forget about C. Suppose I give you a number and ask you to determine if it's prime. How do you do it? Write down the steps clearly, thenworry about translating them into code.

好吧，所以忘记 C。假设我给你一个数字并让你确定它是否是质数。你怎么做呢？清楚地写下这些步骤，然后再担心将它们翻译成代码。

Once you have the algorithm determined, it will be much easier for you to figure out how to write a program, and for others to help you with it.

一旦确定了算法，您就可以更轻松地弄清楚如何编写程序，并让其他人帮助您。

edit:Here's the C# code you posted:

编辑：这是您发布的 C# 代码：

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

This is very nearlyvalid C as is; there's no booltype in C, and no trueor false, so you need to modify it a little bit (edit: Kristopher Johnson correctly points out that C99 added the stdbool.h header). Since some people don't have access to a C99 environment (but you should use one!), let's make that very minor change:

这几乎是有效的 C 语言；boolC 中没有类型，也没有trueor false，因此您需要稍微修改它（编辑：Kristopher Johnson 正确指出 C99 添加了 stdbool.h 标头）。由于有些人无法访问 C99 环境（但您应该使用一个！），让我们做一个非常小的更改：

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

This is a perfectly valid C program that does what you want. We can improve it a little bit without too much effort. First, note that iis always less than number, so the check that i != numberalways succeeds; we can get rid of it.

这是一个完全有效的 C 程序，可以执行您想要的操作。我们可以毫不费力地改进它。首先，注意i总是小于number，所以i != number总是成功的检查；我们可以摆脱它。

Also, you don't actually need to try divisors all the way up to number - 1; you can stop checking when you reach sqrt(number). Since sqrtis a floating-point operation and that brings a whole pile of subtleties, we won't actually compute sqrt(number). Instead, we can just check that i*i <= number:

此外，您实际上并不需要一直尝试除数number - 1；当您到达 sqrt(number) 时，您可以停止检查。由于sqrt是一个浮点运算并且会带来一大堆微妙之处，因此我们实际上不会计算sqrt(number)。相反，我们可以检查一下i*i <= number：

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

One last thing, though; there was a small bug in your original algorithm! If numberis negative, or zero, or one, this function will claim that the number is prime. You likely want to handle that properly, and you may want to make numberbe unsigned, since you're more likely to care about positive values only:

不过，最后一件事是；您的原始算法中有一个小错误！如果number为负数、零或一，则此函数将声明该数为素数。您可能希望正确处理它，并且您可能希望使number未签名，因为您更有可能只关心正值：

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

This definitely isn't the fastest way to check if a number is prime, but it works, and it's pretty straightforward. We barely had to modify your code at all!

这绝对不是检查数字是否为质数的最快方法，但它有效，而且非常简单。我们几乎不需要修改您的代码！

Answer 2

回答by Eric Bainville

Build a table of small primes, and check if they divide your input number.
If the number survived to 1, try pseudo primality tests with increasing basis. See Miller-Rabin primality testfor example.
If your number survived to 2, you can conclude it is prime if it is below some well known bounds. Otherwise your answer will only be "probably prime". You will find some values for these bounds in the wiki page.

建立一个小素数表，并检查它们是否可以划分您输入的数字。
如果数字存活到 1，请尝试增加基数的伪素性测试。例如，参见Miller-Rabin 素性检验。
如果您的数字存活到 2，则如果它低于某个众所周知的界限，您就可以断定它是素数。否则你的答案只会是“可能是素数”。您将在 wiki 页面中找到这些边界的一些值。

Answer 3

回答by Matt Lacey

Check the modulus of each integer from 2 up to the root of the number you're checking.

检查从 2 到您要检查的数字的根的每个整数的模数。

If modulus equals zero then it's not prime.

如果模数为零，则它不是素数。

pseudo code:

伪代码：

bool IsPrime(int target)
{
  for (i = 2; i <= root(target); i++)
  {
    if ((target mod i) == 0)
    {
      return false;
    }
  }

  return true;
}

Answer 4

回答by monksy

I'm suprised that no one mentioned this.

我很惊讶没有人提到这一点。

Use the Sieve Of Eratosthenes

使用埃拉托色尼筛子

Details:

细节：

Basically nonprime numbers are divisible by another number besides 1 and themselves
Therefore: a nonprime number will be a product of prime numbers.

基本上非质数可以被除 1 和它们本身以外的另一个数整除
因此：非质数将是质数的乘积。

The sieve of Eratosthenes finds a prime number and stores it. When a new number is checked for primeness all of the previous primes are checked against the know prime list.

Eratosthenes 的筛子找到一个质数并存储它。当检查一个新数的素数时，所有先前的素数都会根据已知素数列表进行检查。

Reasons:

原因：

This algorithm/problem is known as "Embarrassingly Parallel"
It creates a collection of prime numbers
Its an example of a dynamic programming problem
Its quick!

这个算法/问题被称为“令人尴尬的并行”
它创建了一个质数集合
它是动态规划问题的一个例子
它很快！

Answer 5

回答by Vladimir Kocjancic

I would just add that no even number (bar 2) can be a prime number. This results in another condition prior to for loop. So the end code should look like this:

我只想补充一点，没有偶数（第 2 条）可以是质数。这会导致 for 循环之前的另一个条件。所以最终代码应该是这样的：

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

Answer 6

回答by Olof Forshell

int is_prime(int val)
{
   int div,square;

   if (val==2) return TRUE;    /* 2 is prime */
   if ((val&1)==0) return FALSE;    /* any other even number is not */

   div=3;
   square=9;    /* 3*3 */
   while (square<val)
   {
     if (val % div == 0) return FALSE;    /* evenly divisible */
     div+=2;
     square=div*div;
   }
   if (square==val) return FALSE;
   return TRUE;
}

Handling of 2 and even numbers are kept out of the main loop which only handles odd numbers divided by odd numbers. This is because an odd number modulo an even number will always give a non-zero answer which makes those tests redundant. Or, to put it another way, an odd number maybe evenly divisible by another odd number but neverby an even number (E*E=>E, E*O=>E, O*E=>E and O*O=>O).

2 和偶数的处理被排除在只处理奇数除以奇数的主循环之外。这是因为以偶数为模的奇数将始终给出非零答案，这使得这些测试变得多余。或者，换句话说，一个奇数可以被另一个奇数整除，但不能被偶数整除（E*E=>E，E*O=>E，O*E=>E 和 O*O =>O)。

A division/modulus is really costly on the x86 architecture although how costly varies (see http://gmplib.org/~tege/x86-timing.pdf). Multiplications on the other hand are quite cheap.

尽管成本各不相同，但除法/模数在 x86 架构上的成本确实很高（请参阅http://gmplib.org/~tege/x86-timing.pdf）。另一方面，乘法非常便宜。

Answer 7

回答by Blackhat002

Stephen Canon answered it very well!

史蒂芬佳能回答得很好！

But

但

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3.
This is because all integers can be expressed as (6k + i) for some integer k and for i = ?1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 ≤ √n.

This is 3 times as fast as testing all m up to √n.

int IsPrime(unsigned int number) {
    if (number <= 3 && number > 1) 
        return 1;            // as 2 and 3 are prime
    else if (number%2==0 || number%3==0) 
        return 0;     // check if number is divisible by 2 or 3
    else {
        unsigned int i;
        for (i=5; i*i<=number; i+=6) {
            if (number % i == 0 || number%(i + 2) == 0) 
                return 0;
        }
        return 1; 
    }
}

通过观察除 2 和 3 之外的所有素数都是 6k ± 1 的形式，可以进一步改进算法。
这是因为对于某些整数 k 和对于 i = ?1、0、1、2、3 或 4，所有整数都可以表示为 (6k + i)；2 除 (6k + 0)、(6k + 2)、(6k + 4)；和 3 个除法 (6k + 3)。
因此，更有效的方法是测试 n 是否可以被 2 或 3 整除，然后检查所有形式为 6k ± 1 ≤ √n 的数字。

这比测试所有 m 到 √n 的速度快 3 倍。

int IsPrime(unsigned int number) {
    if (number <= 3 && number > 1) 
        return 1;            // as 2 and 3 are prime
    else if (number%2==0 || number%3==0) 
        return 0;     // check if number is divisible by 2 or 3
    else {
        unsigned int i;
        for (i=5; i*i<=number; i+=6) {
            if (number % i == 0 || number%(i + 2) == 0) 
                return 0;
        }
        return 1; 
    }
}

Answer 8

回答by JerryGoyal

this program is much efficient for checking a single number for primality check.

该程序对于检查单个数字进行素性检查非常有效。

bool check(int n){
    if (n <= 3) {
        return n > 1;
    }

    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
        int sq=sqrt(n); //include math.h or use i*i<n in for loop
    for (int i = 5; i<=sq; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

Answer 9

回答by Dr Beco

After reading this question, I was intrigued by the fact that some answers offered optimization by running a loop with multiples of 2*3=6.

阅读此问题后，我对某些答案通过运行 2*3=6 的倍数提供优化的事实很感兴趣。

So I create a new function with the same idea, but with multiples of 2*3*5=30.

所以我用同样的想法创建了一个新函数，但它是 2*3*5=30 的倍数。

int check235(unsigned long n)
{
    unsigned long sq, i;

    if(n<=3||n==5)
        return n>1;

    if(n%2==0 || n%3==0 || n%5==0)
        return 0;

    if(n<=30)
        return checkprime(n); /* use another simplified function */

    sq=ceil(sqrt(n));
    for(i=7; i<=sq; i+=30)
        if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0 
           || n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0)
            return 0;

        return 1;
}

By running both functions and checking times I could state that this function is really faster. Lets see 2 tests with 2 different primes:

通过运行这两个函数和检查时间，我可以说这个函数真的更快。让我们看看有 2 个不同素数的 2 个测试：

$ time ./testprimebool.x 18446744069414584321 0
f(2,3)
Yes, its prime.    
real    0m14.090s
user    0m14.096s
sys     0m0.000s

$ time ./testprimebool.x 18446744069414584321 1
f(2,3,5)
Yes, its prime.    
real    0m9.961s
user    0m9.964s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 0
f(2,3)
Yes, its prime.    
real    0m13.990s
user    0m13.996s
sys     0m0.004s

$ time ./testprimebool.x 18446744065119617029 1
f(2,3,5)
Yes, its prime.    
real    0m10.077s
user    0m10.068s
sys     0m0.004s

So I thought, would someone gain too much if generalized? I came up with a function that will do a siege first to clean a given list of primordial primes, and then use this list to calculate the bigger one.

所以我想，如果概括的话，有人会得到太多吗？我想出了一个函数，它首先会进行围攻以清除给定的原始素数列表，然后使用这个列表来计算更大的一个。

int checkn(unsigned long n, unsigned long *p, unsigned long t)
{
    unsigned long sq, i, j, qt=1, rt=0;
    unsigned long *q, *r;

    if(n<2)
        return 0;

    for(i=0; i<t; i++)
    {
        if(n%p[i]==0)
            return 0;
        qt*=p[i];
    }
    qt--;

    if(n<=qt)
        return checkprime(n); /* use another simplified function */

    if((q=calloc(qt, sizeof(unsigned long)))==NULL)
    {
        perror("q=calloc()");
        exit(1);
    }
    for(i=0; i<t; i++)
        for(j=p[i]-2; j<qt; j+=p[i])
            q[j]=1;

    for(j=0; j<qt; j++)
        if(q[j])
            rt++;

    rt=qt-rt;
    if((r=malloc(sizeof(unsigned long)*rt))==NULL)
    {
        perror("r=malloc()");
        exit(1);
    }
    i=0;
    for(j=0; j<qt; j++)
        if(!q[j])
            r[i++]=j+1;

    free(q);

    sq=ceil(sqrt(n));
    for(i=1; i<=sq; i+=qt+1)
    {
        if(i!=1 && n%i==0)
            return 0;
        for(j=0; j<rt; j++)
            if(n%(i+r[j])==0)
                return 0;
    }
    return 1;
}

I assume I did not optimize the code, but it's fair. Now, the tests. Because so many dynamic memory, I expected the list 2 3 5 to be a little slower than the 2 3 5 hard-coded. But it was ok as you can see bellow. After that, time got smaller and smaller, culminating the best list to be:

我假设我没有优化代码，但这是公平的。现在，测试。由于动态内存太多，我预计列表 2 3 5 会比硬编码的 2 3 5 慢一点。但是没关系，正如你在下面看到的那样。在那之后，时间越来越短，最终最好的名单是：

2 3 5 7 11 13 17 19

With 8.6 seconds. So if someone would create a hardcoded program that makes use of such technique I would suggest use the list 2 3 and 5, because the gain is not that big. But also, if willing to code, this list is ok. Problem is you cannot state all cases without a loop, or your code would be very big (There would be 1658879 ORs, that is ||in the respective internal if). The next list:

8.6 秒。因此，如果有人会创建一个使用这种技术的硬编码程序，我建议使用列表 2 3 和 5，因为收益不是那么大。而且，如果愿意编码，这个列表是可以的。问题是你不能在没有循环的情况下陈述所有情况，或者你的代码会非常大（会有 1658879 ORs，即||在各自的内部if）。下一个列表：

2 3 5 7 11 13 17 19 23

time started to get bigger, with 13 seconds. Here the whole test:

时间开始变长，有 13 秒。这里是整个测试：

$ time ./testprimebool.x 18446744065119617029 2 3 5
f(2,3,5)
Yes, its prime.
real    0m12.668s
user    0m12.680s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7
f(2,3,5,7)
Yes, its prime.
real    0m10.889s
user    0m10.900s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11
f(2,3,5,7,11)
Yes, its prime.
real    0m10.021s
user    0m10.028s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13
f(2,3,5,7,11,13)
Yes, its prime.
real    0m9.351s
user    0m9.356s
sys     0m0.004s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17
f(2,3,5,7,11,13,17)
Yes, its prime.
real    0m8.802s
user    0m8.800s
sys     0m0.008s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19
f(2,3,5,7,11,13,17,19)
Yes, its prime.
real    0m8.614s
user    0m8.564s
sys     0m0.052s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23
f(2,3,5,7,11,13,17,19,23)
Yes, its prime.
real    0m13.013s
user    0m12.520s
sys     0m0.504s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29
f(2,3,5,7,11,13,17,19,23,29)                                                                                                                         
q=calloc(): Cannot allocate memory

PS. I did not free(r) intentionally, giving this task to the OS, as the memory would be freed as soon as the program exited, to gain some time. But it would be wise to free it if you intend to keep running your code after the calculation.

附注。我没有故意释放（r），将这个任务交给操作系统，因为一旦程序退出，内存就会被释放，以获得一些时间。但是如果你打算在计算后继续运行你的代码，那么释放它是明智的。

BONUS

奖金

int check2357(unsigned long n)
{
    unsigned long sq, i;

    if(n<=3||n==5||n==7)
        return n>1;

    if(n%2==0 || n%3==0 || n%5==0 || n%7==0)
        return 0;

    if(n<=210)
        return checkprime(n); /* use another simplified function */

    sq=ceil(sqrt(n));
    for(i=11; i<=sq; i+=210)
    {    
        if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 || 
   n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 || 
   n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 || 
   n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 || 
   n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 || 
   n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 || 
   n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 || 
   n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 || 
   n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 || 
   n%(i+188)==0 || n%(i+198)==0)
            return 0;
    }
    return 1;
}

Time:

时间：

$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real    0m9.123s
user    0m9.132s
sys     0m0.000s

Answer 10

回答by S_R

Using Sieve of Eratosthenes, computation is quite faster compare to "known-wide" prime numbers algorithm.

使用埃拉托色尼筛法，与“已知范围”素数算法相比，计算速度要快得多。

By using pseudocode from it's wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), I be able to have the solution on C#.

通过使用它的 wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 中的伪代码，我可以在 C# 上找到解决方案。

public bool IsPrimeNumber(int val) {
    // Using Sieve of Eratosthenes.
    if (val < 2)
    {
        return false;
    }

    // Reserve place for val + 1 and set with true.
    var mark = new bool[val + 1];
    for(var i = 2; i <= val; i++)
    {
        mark[i] = true;
    }

    // Iterate from 2 ... sqrt(val).
    for (var i = 2; i <= Math.Sqrt(val); i++)
    {
        if (mark[i])
        {
            // Cross out every i-th number in the places after i (all the multiples of i).
            for (var j = (i * i); j <= val; j += i)
            {
                mark[j] = false;
            }
        }
    }

    return mark[val];
}

IsPrimeNumber(1000000000) takes 21s 758ms.

IsPrimeNumber(1000000000) 需要 21 秒 758 毫秒。

NOTE: Value might vary depend on hardware specifications.

注意：值可能因硬件规格而异。

C# C - 判断一个数是否为素数

提问by Jimmy

采纳答案by Stephen Canon

回答by Eric Bainville

回答by Matt Lacey

回答by monksy

回答by Vladimir Kocjancic

回答by Olof Forshell

回答by Blackhat002

回答by JerryGoyal

回答by Dr Beco

回答by S_R

相关推荐

最近更新

标签

C# C - 判断一个数是否为素数

提问by Jimmy

采纳答案by Stephen Canon

回答by Eric Bainville

回答by Matt Lacey

回答by monksy

回答by Vladimir Kocjancic

回答by Olof Forshell

回答by Blackhat002

回答by JerryGoyal

回答by Dr Beco

回答by S_R

相关推荐

C# 使用窗口句柄在最上面创建一个窗口

C# 将 List<int> 转换为逗号分隔的字符串

C# 反模式

C# app.config 文件中的多个 SQL Server 连接字符串

相关推荐

最近更新

标签