判断一个数是否为素数
“素数和质数没有区别，素数又叫质数，质数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。比1大但不是素数的数称为合数，1和0既非素数也非合数。”
所谓素数，是指除了1和其本身外，不能被其它任何整数整除的正整数，2是最小的素数。
现在，用户输入一个整数，判断它是否为素数。
方法1
是指除了1和其本身外，不能被其它任何整数整除的正整数
for循环遍历2~输入的数值num，num对这些数取余（求模），余数是0代表能整除，代表不是素数，如果不是素数，标志位置1，跳出循环判断标志位的状态即可
1. #include <stdio.h> 2. 3. int main(void) { 4. int i, j; 5. int num; 6. char flag = 0; //0代表是素数，1代表不是 7. scanf("%d", &num); //输入 8. 9. for (i = 2; i < num; i++) { 10. if (num % i == 0) { //如果能整除，标志位置1 11. flag = 1; 12. } 13. } 14. 15. if (flag == 1) //判断标志位即可知是否为素数 16. printf("%d不是素数\n", num); 17. else 18. printf("%d是素数\n", num); 19. return 0; 20. }
方法2
当一个数不是质数时，必定存在两个约数，一个大于等于sqrt(n)，另一个小于sqrt(n)。利用这种特性，可以对方法1进行改进，只判断数n能否被小于sqrt(n)的数整除。
小于平方根和大于平方根的部分是一一对应的，因而可以只判断从2到平方根的数字是否都能被整除即可。
2.1
1. #include <stdio.h> 2. #include <math.h> 3. 4. int main() { 5. int num, k, i; 6. char flag = 0; 7. scanf("%d", &num); 8. 9. k = sqrt(num); //先开平方，减小运算量 10. for (i = 2; i <= k; i++) { 11. if (num % i == 0) { 12. flag = 1; 13. break; //只要有能整除的数，就跳出循环判断，减小运算量 14. } 15. } 16. 17. if (flag == 1) //判断标志位即可知是否为素数 18. printf("%d不是素数\n", num); 19. else 20. printf("%d是素数\n", num); 21. return 0; 22. }
2.2
1. #include <stdio.h> 2. #include <math.h> 3. 4. int main() { 5. int m, k, i; 6. scanf("%d", &m); 7. 8. k = sqrt(m); 9. for (i = 2; i <= k; i++) { 10. if (m % i == 0) //只要有能整除的数，就跳出循环判断，减小运算量 11. break; 12. } 13. 14. if (m >= 2) { 15. if (i > k) 16. printf("%d is a prime.", m); 17. else 18. printf("%d is not a prime.", m); 19. } else 20. printf("%d is not a prime.", m); 21. return 0; 22. }
进阶：输出区间长度内的素数
比如打印1000到2000内的素数
1. #include <stdio.h> 2. 3. int main() { 4. int i = 1000; 5. while (i <= 2000) { 6. int flag = 0; 7. int j = 2; 8. 9. while (j < i) { 10. if (i % j == 0) { 11. flag += 1; 12. } 13. j = j + 1; 14. } 15. if (flag == 0) { 16. printf("%d\n", i); 17. } 18. i = i + 1; 19. } 20. printf("\n"); 21. return 0; 22. }
用函数封装一下，直接调用这个函数即可输出素数
1. #include <stdio.h> 2. 3. void prime(int x, int y) // 区间（x，y） 4. { 5. int num; // 当前判断的数 6. char flag = 0; 7. // 外层循环，遍历区间（x，y）内的数 8. for (int j = x; j <= y; j++) 9. { 10. num = j; 11. 12. // 内层循环，判断当前数，是否为素数 13. for (int i = 2; i < num; i++) 14. { 15. if (num % i == 0) // 能整除，就不是素数 16. { 17. flag = 1; 18. break; // 跳出内层循环，遍历下一个数 19. } 20. } 21. 22. if (flag == 0) 23. printf("%d\n", num); 24. 25. flag = 0; // 在判断下一个数之前，先把标志位置0 26. } 27. } 28. 29. int main() 30. { 31. prime(1000, 2000); 32. }
