-5

我不明白我们为什么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;
}
4

3 回答 3

1

该函数会告诉您最终用户输入的数字之后的下一个素数。该isPrime变量用作布尔“标志”，可让您将有关在循环内找到的条件的信息传递给在该循环外运行的代码。

内部for循环尝试连续奇数作为除数候选。当它找到一个除数时，它需要通过将标志设置为 来使外部do/while循环知道已找到除数（因此候选不是素数）这一事实。外部循环检查该标志，并且仅当在范围内的所有候选者都用尽后它仍然存在时才存在循环。isPrimefalsetrue3..sqrt(candidate)

于 2013-07-29T13:46:33.320 回答
0 
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.

代码序列总结：

什么是质数：

素数（或素数）是大于 1 的自然数，除了 1 和它本身之外没有正除数。大于 1 且不是素数的自然数称为合数。

例如，5 是素数，因为只有 1 和 5 能将它整除，而 6 是合数，因为它除了 1 和 6 之外还有除数 2 和 3

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;
于 2013-07-29T15:19:14.830 回答
0

改写成更易读的东西：

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 );
}
于 2013-07-29T14:00:43.963 回答