c - Prime Number program

Question

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.

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 - 1 in for loop. If I will give the input 11 then it will end up on 11 - 1 = 10 then how it will give up the logic of if(c == n) { printf("%d", n);?

Answer 1

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

现在正确理解你的 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} 

根据 for 循环条件，当value 等于c <= n - 1时循环中断。所以 if is equals to 循环条件对于to为真，在每次迭代中增加一（使用增量）当变为（ot say ）然后条件变为假并且循环中断。cnn11c = 2c = 10cc++c11nc <= n - 1

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

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

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

---

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

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

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

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

Answer 2

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

这就是为什么。循环是这样工作的：

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

示例：假设您n是 3。

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 == 3c == n

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

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

n如果除 1 和它本身有一个除数，n就不能是素数。因此，如果您击中任何c等于1 < c < n0n%c的值n，则不能是素数。

提示：您不必测试大于√n.

Answer 3

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

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

Answer 4

想想当你说一个数是素数时它意味着什么。一个数 p 是素数，当对于每个n>1, n<p，余数r = 0对于p/n = r。

因此，此循环遍历每个值 (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");

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

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

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

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

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