目录
判断一个数是否为素数
方法1
方法2
2.1
2.2
进阶:输出区间长度内的素数
判断一个数是否为素数
“素数和质数没有区别,素数又叫质数,质数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。比1大但不是素数的数称为合数,1和0既非素数也非合数。”
所谓素数,是指除了1和其本身外,不能被其它任何整数整除的正整数,2是最小的素数。
现在,用户输入一个整数,判断它是否为素数。
方法1
是指除了1和其本身外,不能被其它任何整数整除的正整数
for循环遍历2~输入的数值num,num对这些数取余(求模),余数是0代表能整除,代表不是素数,如果不是素数,标志位置1,跳出循环判断标志位的状态即可
#include <stdio.h>
int main(void) {
int i, j;
int num;
char flag = 0; //0代表是素数,1代表不是
scanf("%d", &num); //输入
for (i = 2; i < num; i++) {
if (num % i == 0) { //如果能整除,标志位置1
flag = 1;
}
}
if (flag == 1) //判断标志位即可知是否为素数
printf("%d不是素数\n", num);
else
printf("%d是素数\n", num);
return 0;
}
方法2
当一个数不是质数时,必定存在两个约数,一个大于等于sqrt(n),另一个小于sqrt(n)。利用这种特性,可以对方法1进行改进,只判断数n能否被小于sqrt(n)的数整除。
小于平方根和大于平方根的部分是一一对应的,因而可以只判断从2到平方根的数字是否都能被整除即可。
2.1
#include <stdio.h>
#include <math.h>
int main() {
int num, k, i;
char flag = 0;
scanf("%d", &num);
k = sqrt(num); //先开平方,减小运算量
for (i = 2; i <= k; i++) {
if (num % i == 0) {
flag = 1;
break; //只要有能整除的数,就跳出循环判断,减小运算量
}
}
if (flag == 1) //判断标志位即可知是否为素数
printf("%d不是素数\n", num);
else
printf("%d是素数\n", num);
return 0;
}
2.2
#include <stdio.h>
#include <math.h>
int main() {
int m, k, i;
scanf("%d", &m);
k = sqrt(m);
for (i = 2; i <= k; i++) {
if (m % i == 0) //只要有能整除的数,就跳出循环判断,减小运算量
break;
}
if (m >= 2) {
if (i > k)
printf("%d is a prime.", m);
else
printf("%d is not a prime.", m);
} else
printf("%d is not a prime.", m);
return 0;
}
进阶:输出区间长度内的素数
比如打印1000到2000内的素数文章来源:https://www.toymoban.com/news/detail-440485.html
#include <stdio.h>
int main() {
int i = 1000;
while (i <= 2000) {
int flag = 0;
int j = 2;
while (j < i) {
if (i % j == 0) {
flag += 1;
}
j = j + 1;
}
if (flag == 0) {
printf("%d\n", i);
}
i = i + 1;
}
printf("\n");
return 0;
}
用函数封装一下,直接调用这个函数即可输出素数文章来源地址https://www.toymoban.com/news/detail-440485.html
#include <stdio.h>
void prime(int x, int y) // 区间(x,y)
{
int num; // 当前判断的数
char flag = 0;
// 外层循环,遍历区间(x,y)内的数
for (int j = x; j <= y; j++)
{
num = j;
// 内层循环,判断当前数,是否为素数
for (int i = 2; i < num; i++)
{
if (num % i == 0) // 能整除,就不是素数
{
flag = 1;
break; // 跳出内层循环,遍历下一个数
}
}
if (flag == 0)
printf("%d\n", num);
flag = 0; // 在判断下一个数之前,先把标志位置0
}
}
int main()
{
prime(1000, 2000);
}
到了这里,关于【C语言】判断一个数是否为素数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!