C语言 质数程序

Prime Number program

提问by Tayyab Gulsher Vohra

I want to make a program in C language which will take the user input and I would not be able to understand the logic of the loop.

我想用 C 语言编写一个程序，它将接受用户输入，但我无法理解循环的逻辑。

for ( c = 2 ; c <= n - 1 ; c++ )

The program code is given below:-

程序代码如下：-

#include<stdio.h>
#include<conio.h>

void main()
{
   int n, c;

   printf("Enter a number to check if it is prime\n");
   scanf("%d", &n);

   for ( c = 2 ; c <= n - 1 ; c++ )
   {
      if ( n % c == 0 )
      {
         printf("%d is not prime.\n", n);
         break;
      }
   }
   if ( c == n )
      printf("%d is prime.\n", n);

   getch();
}

I have used the for loop which will end up the statement of n - 1in for loop. If I will give the input 11then it will end up on 11 - 1 = 10then how it will give up the logic of if(c == n) { printf("%d", n);?

我使用了 for 循环，它将结束n - 1in for 循环的语句。如果我给出输入，11那么它最终11 - 1 = 10会如何放弃逻辑 if(c == n) { printf("%d", n);？

回答by Grijesh Chauhan

If I will give the input 11then it will end up on 11 - 1 = 10then how it will give up the logic of if(c == n) { printf("%d", n);?

如果我给出输入，11那么它最终11 - 1 = 10会如何放弃逻辑 if(c == n) { printf("%d", n);？

Now correctly understand your for loop condition:

现在正确理解你的 for 循环条件：

for ( c = 2 ; c <= n - 1 ; c++ )
              ^^^^^^^^^^^^
              2 <= 11 - 1  -> True   // {for block executes }
              3 <= 11 - 1  -> True   // {for block executes }
                 :
                 :
              9 <= 11 - 1  -> True   // {for block executes }
              10 <= 11 - 1  -> True  // {for block executes }
              11 <= 11 - 1  -> False  breaks //{And Now for block NOT executes}

if (c == n)
    ^^^^^^
   11 == 11 -> True  // {if block executes} 

According to for loop condition c <= n - 1, loop breaks when cvalue becomes equals to n. So if nis equals to 11loop condition is true for c = 2to c = 10, in each iteration cincrements by one (using c++increment) when cbecomes 11(ot say n) then condition c <= n - 1become false and loop breaks.

根据 for 循环条件c <= n - 1，当c值变为等于时循环中断n。因此，如果nis 等于 11循环条件对c = 2to为真c = 10，则在每次迭代中c，c++当c变成11（或者说n）时，每次迭代递增一（使用增量），然后条件c <= n - 1变为假并且循环中断。

In if condition (after for loop) cvalue compared with n. that is:

在 if 条件（for 循环之后）中的c值与n. 那是：

if ( c == n )
//   11 == 11  that is true

for n= 11it becomes and c= 11if condition evaluates true and printf()associated with if executes.

for n=11它变成 and c= 11if 条件评估为真并printf()与 if 执行相关联。

---

---

It is also important to understand that the for-loop only terminates for c = nwhen nis a prime number, but if suppose nis a non-prime number then for-loop will break for cvalue less then n - 1due to break;statement in nested ifblock in for-loop.

理解 for 循环仅c = n在n是素数时才终止也很重要，但是如果假设n是非素数，c那么n - 1由于for 循环break;中嵌套if块中的语句，for 循环将因小于值而中断。

for( c = 2; c <= n - 1; c++ ) 
{
  if(n % c == 0)<=="for Non-prime `n`, if condition will be true for some `c < n - 1`"
  {  ^^^^^^^^^^^ True 
     printf("%d is not prime.\n", n);
     break; <== "move control outside for-loop"
  }  //      | 
}    //      |
// <---------+ // if break; executes control moves here with c < n - 1
if (c == n)<== "this condition will evaluates FALSE"  
   ^^^^^^^^ False

For example if n = 8then in very first iteration of for-loop with value c = 2if condition if(n % c == 0)that evaluates as if(8 % 2 == 0)== if( 0 == 0)= True and break;statement inside if-block moves control outside for-loop(as shown in figure).

例如，如果n = 8在 for 循环的第一次迭代中，c = 2如果条件if(n % c == 0)评估为if(8 % 2 == 0)== if( 0 == 0)= True 并且break;if 块中的语句将控制移到 for 循环之外（如图所示）。

Because this time for loop not terminated due to c <= n - 1condition but braked because of if(n % c == 0)so out-side for-loop cvalue is less than nhence if (c == n)evaluates as False.

因为这次 for 循环没有因c <= n - 1条件而终止，而是因为 if(n % c == 0)外部 for-loopc值小于n所以 if (c == n)评估为 False。

回答by TheMorph

The for loop loops from c = 2to c = n - 1except it hit's the breakstatement. If it does, it will jump out of the loop. If you never break then your cwill actually be nafterthe loop.

for 循环从c = 2to循环，c = n - 1除了它命中的是break语句。如果是，它将跳出循环。如果您从不中断，那么您c实际上将n在循环之后。

And here is why. The loop works like this:

这就是原因。循环是这样工作的：

1. initialize the for loop with c = 2
2. Check for condition (c <= n - 1)if true: execute loop body if false: jump past loop
3. increment cby one
4. goto 2.

1. 初始化 for 循环 c = 2
2. 检查条件(c <= n - 1)如果为真：执行循环体如果为假：跳过循环
3. 加c一
4. 转到 2。

Example: Suppose your nis 3.

例子：假设你n是 3。

1. we set cto 2, now c == 2and n == 3
2. 2 <= 3 - 1is true, so the loop body will be executed
3. we increment c by 1, now c == 3and n == 3
4. we go back to 2. in the description
5. 3 <= 3 - 1is false, so we don't execute the loop body now and jump out of the loop
6. after we left the loop c == 3and n == 3so c == n

1. 我们设置c为 2，现在c == 2和n == 3
2. 2 <= 3 - 1为真，所以循环体将被执行
3. 我们将 c 增加 1，现在c == 3和n == 3
4. 我们回到 2. 在描述中
5. 3 <= 3 - 1为假，所以我们现在不执行循环体并跳出循环
6. 之后我们离开了循环c == 3和n == 3使c == n

So if we never hit the break statement cwill be equal to nafter the loop. We hit the break statement ifn is not prime. If we break cwill miss at leastone increment and thus c < nafter the loop. Now c == nwill evaluate to false and the if statements body of if ( c == n )will not be executed.

所以如果我们从来没有碰到过 break 语句c将等于n循环之后。如果n 不是素数，我们就会执行 break 语句。如果我们 breakc将错过至少一个增量，因此c < n在循环之后。现在c == n将评估为 false 并且if ( c == n )不会执行if 语句主体。

Now to the if ( n%c == 0 ). n%cmeans nmodulo c, so the remainder of the division of nby c. If this remainder is 0 then cis an integer divisor of n. So in the loop you are testing nfor any divisor bigger than 1 and smaller than n.

现在到if ( n%c == 0 ). n%c装置n模c，所以的除法的余数n通过c。如果此余数为 0，c则为 的整数除数n。因此，在循环中，您正在测试n任何大于 1 且小于 的除数n。

If there is a divisor of nexcept 1 and itself, ncan't be prime. So if you hit any cwith 1 < c < nthat makes n%cequal to 0 ncan't be prime.

如果有一个n除 1 和它本身的约数，n则不能是素数。所以如果你命中任何一个c，1 < c < n那么n%c等于 0n就不能是素数。

Hint: You don't have to test for divisors bigger than √n.

提示：您不必测试大于 的除数√n。

回答by jk.

Your assumption that cends up being n - 1is incorrect. If you step through your program with the debugger you should see that for n == 11, c == 11at the end of the loop.

你的假设c最终n - 1是不正确的。如果您使用调试器单步执行程序，您应该会在循环结束时看到 for n == 11, c == 11。

If we don't break early then the last time the loop body executes is indeed when c == n - 1however cis then incremented and the loop invariant test fails so after the loop c == n.

如果我们不早点中断，那么最后一次循环体执行确实是当c == n - 1但是c然后递增并且循环不变测试在循环之后失败c == n。

回答by ChuckCottrill

Consider what it means when you say that a number is prime. A number p is prime when for every n>1, n<p, the remainder r = 0for p/n = r.

考虑一下当你说一个数是素数时这意味着什么。一个数 p 是素数，当为每个n>1, n<p，余数r = 0为p/n = r。

So, this loop runs through each value (c) the range [2..p-1], testing for the remainder.

所以，这个循环遍历每个值 (c) range [2..p-1]，测试余数。

int isprime = 1; //use a flag to indicate prime, assume prime until proven otherwise
for ( c = 2 ; //initialize c=2, the first value in the range [2..p-1]
      c <= n - 1 ; //check whether c is still in the range [2..p-1]
      c++ ) //increment c to the next value in the range [2..p-1]
{
    if ( n % c == 0 ) //modulo '%' is the remainder of the integer division
    {
        isprime = 0;
        break;
    }
}
printf("%d %s prime.\n", n, isprime?"is":"is not");

Rather than test that the number is prime by checking a side effect of the loop counter, why not set a flag before the loop, and then test it as the decision for prime at the end? The result is code that is less fragile, error-prone, and clearer.

与其通过检查循环计数器的副作用来测试数字是否为素数，为什么不在循环之前设置一个标志，然后在最后测试它作为素数的决定？结果是代码不那么脆弱、容易出错且更清晰。

Want to save about half the work? Once you test n%2, we know that there is no number k such that k*2=n, right? so check the range [2..p/2], and change your loop to,

想要节省大约一半的工作吗？一旦你测试n%2，我们就知道没有数字 k 是这样的k*2=n，对吧？所以检查范围[2..p/2]，并将循环更改为，

for( c = 2; c <= n/2; c++ )

Can you think of a number smaller than n/2that works?

你能想出比n/2这更小的数字吗？

An interesting algorithm for finding multiple primes is the Sieve of Erastosthenes.

寻找多个素数的一个有趣的算法是Erastosthenes 筛法。