判断一个数是否为素数
“素数和质数没有区别,素数又叫质数,质数是指在大于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. }