素数/质数的判断(C++)

思路：判断一个整数n是否为素数，只需用2到n-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。

判断定理：“n不能够被不大于根号n的任何素数整除，则n是一个素数”

用代买表示如下：

int is_prime = trure;

int i = 2;

while (i <= (sqrt(n)))　　// 当i小于n的平方根时

{　　　　　　　　　　　　

　　　if (n % i == 0)　　// 如果i处以n等于0，

　　　　is_prime == false;　　// i不是素数

　　i++;　　　　　　　　// 把i加1

}

完整代码：

 1 #include <iostream>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;    // Number to test for prime-ness
 9     int i;    // Loop counter
10     int is_prime = true;    // Boolean flag...
11                             // Assume true for now.
12 
13     // Get a number from the keyboard.
14 
15     cout << "Enter a number and press ENTER: ";
16     cin >> n;
17 
18     // Test for prime by checking for divisibility
19     // by all whole numbers from 2 to sqrt(n).
20 
21     i = 2;
22     while (i <= sqrt(n))    // While i is <=  sqrt(n).
23     {
24         if (n % i == 0)        // If i divides n,
25             is_prime = false; // n is not prime
26         i++;                // add 1 to i.
27     }
28 
29     // print results
30     if (i <= sqrt(n))
31         cout << "Number is prime." << endl;
32     else 
33         cout << "Number is not prime." << endl;
34 
35     return 0;
36 }

View Code

优化：

　　这个程序可以在找到第一个余数为0的数之后，即使推出循环，而不是继续循环下去，那只会浪费CPU资源。