爲什麼我們在這裏使用bool？

Question

我不明白爲什麼我們在這裏使用bool isPrime，這個函數做了什麼。

{ 
    bool isPrime; 
    int  startingPoint, candidate, last, i; 

    startingPoint = 856; 
    if (startingPoint < 2) 
    { 
    candidate = 2; 
    } 
    else 
    if (startingPoint == 2) 
    { 
    candidate = 3; 
    } 
    else 
    { 
    candidate = startingPoint; 
    if (candidate % 2 == 0)   
    candidate--; 
    do 
    { 
      isPrime = true;     
      candidate += 2;     
      last = sqrt(candidate);  
      for (i = 3; (i <= last) && isPrime; i += 2) 
      { 
       if ((candidate % i) == 0) 
        isPrime = false; 
      } 
     } while (! isPrime); 
    } 

    printf("The next prime after %d is %d. Happy?\n", 
      startingPoint, candidate); 
    return 0; 
} 

Answer 1

isPrime is being used to exit from the for loop & do while loop by conditionally. 

1. in For Loop 

    Our goal is to find out the next greater prime number of candidate. 

    If we have the 25 as candidate, we are going to execute the for loop upto 3 to 5(sqrt of 25). 

    if we found that any number between that value(3 , 5) 
     divides the candidate and gave the remaining as 0. 
     then the candidate was not prime number. 
     So exit the from the for loop by flag setting isPrime to false. 
     next time the for loop will not be executed because , 
     for loop condition fails. 

    Control moves to while loop and checks condition, 
      still we didn't find out the prime number & do while condition 
      is true by (!isPrime) where isPrime is false (!false == Yes) 
      so while loop again executing from the starting of the loop. 


2. in Do while loop 

    To exit from the do while loop , 
    the condition should be failed, 
    that means isPrime should be always true for 3, 5 in for loop. 

    So for loop will entirely run upto the maximum of last value. 

    No chance of setting up the isPrime to false on the for loop. 

    so it will exit from the do while loop. 
    Otherwise it will never sleep until find out the next prime number. 
    it will be infinity. 

I hope it will help you to understand the 
code sequence & why we are using the isPrime flag on the code sequence. 

代碼序列總結：

What is Prime Number：

素數（或素數）是自然數大於1的除1和本身之外沒有任何正數除數。大於1的不是質數的自然數稱爲合數。

例如，5是質數，因爲只有1和5整除它，而6是複合材料，因爲它有另外的除數2和3比1和6

bool isPrime; 
int  startingPoint, candidate, last, i; 

startingPoint = 24; 

//If start point less than 2 
if (startingPoint < 2) { 

    //take candidate as 2 
    candidate = 2; 
} 
//If start point equals 2 

else if (startingPoint == 2) { 
    //take candidate as 3 
    candidate = 3; 
} 
else { 


//if none of the above condition then have startingPoint as candidate 

    candidate = startingPoint; 
    //candiate 24 

    if (candidate % 2 == 0)    /* Test only odd numbers */ 
     candidate--;//if the candidate is even number then make it to odd number by -1 which will be 23 

    do { 

     isPrime = true;     /* Initially we are assuming that the Number 23 is prime number.*/ 

     candidate += 2;     /* Bump to the next number(23+2 =25) to test */ 
     //candidate 25 

     last = sqrt(candidate);  
     //last 5 


     Everytime we will do process the 'for' loop upto sqrt of the candidate. 
     //candidate 25 
     //last 5 

     So If we found the any number between the 3 to 5 not prime number, then we no need to run the for loop till the end. 

     Because we need to find out the nearest next prime number. So no need to waste our CPU usage. 

     // Both 3<=5 && isPrime should be true. 

     //last 3<=5 && true(we assumed it will be a prime number initially) 
     for (i = 3; (i <= last) && isPrime; i += 2) {  
      if ((candidate % i) == 0)      
       isPrime = false; 
     //here increase the 3 to 5 by (i+2), So again it will be executed. But third time it will fail the first condition. 
     //So go to start of do while loop, and so on it will work 
     //Next time candidate will be increased by 2 which will be (25+2) = 27 and failed to find out the prime Number. 
     //Next time candidate will be increased by 2 which will be (27+2) = 29 and success 29 is prime number. 

     } 

    } while (! isPrime);// if the condition true then go to "do" statement. 
} 

printf("The next prime after %d is %d. Happy?\n", 
     startingPoint, candidate); 
return 0; 

Answer 2

該函數告訴您最終用戶輸入的數字後面的下一個素數。 isPrime變量用作布爾「標誌」，它允許您將有關在循環內部找到的條件的信息傳遞給在該循環外部運行的代碼。

內部for循環嘗試連續奇數作爲除數候選。當它找到一個除數時，它需要通過將isPrime標誌設置爲false來確定除數已被找到（因此候選不是總數），這一事實對外部do/while循環已知。外循環會檢查該標誌，並且僅在範圍內的所有候選項已用完時才存在循環。

Answer 3

改寫成更多的東西可讀：

bool isOddNumberPrime(int number) { 
    assert(number & 2 != 0); 

    int i, limit; 

    int limit = sqrt(number);  

    //note that this kind of test is terribly ineffective 
    for (i = 3; (i <= limit); i += 2) { 
     if ((number % i) == 0) { 
      return false; 
     } 
    } 

    return true; 
} 

int getFirstGreaterPrime(int startingPoint) { 
    int candidate; 

    if (startingPoint < 2) { 
     return 2; 
    } 
    else if (startingPoint == 2) { 
     return 3; 
    } 
    else if (candidate % 2 == 0) { 
     candidate = startingPoint + 1; 
    } 
    else { 
     candidate = startingPoint + 2; 
    } 

    //candidate holds a greater odd number 

    while (!isOddNumberPrime(candidate)) { 
     candidate += 2;     
    } 

    return candidate; 
} 

void main() { 
    int number, nextPrime; 

    number = 856; 
    nextPrime = getFirstGreaterPrime(number); 

    printf("The next prime after %d is %d. Happy?\n", 
     number, nextPrime); 
}