素數編程

Question

我想用C語言編寫一個程序，它將接受用戶輸入，我無法理解循環的邏輯。

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

程序代碼如下： -

#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(); 
} 

我已經使用了for循環將在for循環結束的n - 1聲明。如果我將輸入11那麼它將最終在11 - 1 = 10那麼它將如何放棄if(c == n) { printf("%d", n);的邏輯？

Answer 1

如果我會給輸入11那麼它最終會在11 - 1 = 10那麼它將如何放棄邏輯if(c == n) { printf("%d", n);？

現在正確地理解你的循環條件：

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循環條件c <= n - 1，環斷裂時c值變爲等於n。所以，如果n是等於11循環條件爲真爲c = 2到c = 10，在每次迭代c遞增一個（使用c++增量）時c成爲11（OT說n），那麼條件c <= n - 1變成假，循環中斷。

如果條件（在循環後）c值與n相比較。那就是：

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

爲n = 11變得和c = 11如果條件判斷爲真，並與執行如果相關聯printf()。

---

同樣重要的是要明白，for循環只有終止對c = n時n是一個素數，但如果假設n是一個非素數則環將打破c值小於n - 1由於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 

例如，如果n = 8然後用值c = 2 for循環的非常第一次迭代，如果計算結果作爲if(8 % 2 == 0) == if(0 == 0) = True和break;語句內條件if(n % c == 0)如果-塊移動控制以外的for循環（如如圖所示）。

因爲這個時候for循環沒有終止由於c <= n - 1條件，但制動因爲if(n % c == 0)所以出側for循環c值小於n因此if (c == n)計算結果爲假。

Answer 2

for循環從c = 2到c = n - 1循環，除了命中的break語句。如果有，它會跳出循環。如果你永遠不會破，那麼你的c其實n後循環。

這就是爲什麼。循環是這樣的：

1. 與c = 2
2. 檢查初始化for循環條件(c <= n - 1) 如果屬實：由一個
3. 轉到跳過去環路
4. 增量c：執行，如果假循環體 2.

示例：假設您的n是3.

1. 我們設置c 2，現在c == 2和n == 3
2. 2 <= 3 - 1是真實的，那麼循環體將被執行
3. 我們增加1℃，現在c == 3和n == 3
4. 我們回去2在描述中
5. 3 <= 3 - 1是錯誤的，所以我們現在不執行循環體並跳出循環
6. 我們離開循環後c == 3和n == 3所以c == n

因此，如果我們從不打break語句c將在循環後等於n。如果 n不是素數，我們會打破。如果我們打破c將錯過至少一個增量，因此在循環後c < n。現在c == n將評估爲false，並且if (c == n)的if語句正文將不會執行。

現在到if (n%c == 0)。 n%c意味着n模c，所以n的劃分的其餘部分由c。如果這個餘數是0，則c是n的整數除數。因此，在循環中，對於大於1且小於n的任何除數，您正在測試n。

如果除了1和它本身有n的除數，n不能爲素數。所以如果你打與1 < c < n這使得n%c等於0 n不能是素數。提示：您不必測試大於√n的除數。

Answer 3

你的假設c結果爲n - 1是不正確。如果使用調試器逐步執行程序，則應在循環結束時看到n == 11，c == 11。

如果我們不早破，則最後一次循環體執行確實是當c == n - 1然而c進行增量和循環c == n後的循環不變測試失敗等等。

Answer 4

考慮一下當你說一個數字是素數時它的含義。 對於p/n = r，每個n>1, n<p，其餘r = 0的數字p是素數。

因此，此循環遍歷每個值（c）範圍[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的作品更小的？

尋找多個素數的有趣算法是Sieve of Erastosthenes。