素数/质数的判断(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资源。

int is_prime = trure;

int i = 2;

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

{

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

{

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

break; // 不是素数，立即结束循环。

}

i++; // 把i加1

}

}
原文链接: https://www.cnblogs.com/wuzhenbo/archive/2012/04/26/2470357.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍