试除法判定质数 c语言

试除法是一种简单的判断一个较大整数是否为质数的传统算法。它的基本思想是，如果一个大于1的自然数n能被小于它的任何数整除（除了1和它本身），那么这个数就不是质数。在C语言中，可以编写一个函数来实现这个过程：

#include <stdio.h>

// 判断一个数是否为质数的函数
int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1和所有负数都不是质数
    }
    for (int i = 2; i * i <= n; i++) { // 只需检查到√n即可，因为因子成对存在
        if (n % i == 0) {
            return 0; // 如果找到因子，说明n不是质数
        }
    }
    return 1; // 没有找到因子，n可能是质数
}

int main() {
    int num;
    printf("请输入一个正整数：");
    scanf("%d", &num);

    if (isPrime(num)) {
        printf("%d是质数。\n", num);
    } else {
        printf("%d不是质数。\n", num);
    }

    return 0;
}

在这个程序中，用户输入一个整数，`isPrime()`函数会使用试除法检测该数字是否为质数。如果能在2到√n的范围内找到能整除该数的i，那么就是合数，否则它是质数。

相关问题

判断是否为素数c语言

### 判断素数的三种方法

#### 方法一：遍历所有可能因子
通过遍历从1到该数之间所有的整数，统计其因数的数量。如果一个数仅有两个正因数（1和自身），则它是素数。

#include<stdio.h>
int main() {
    int i, m;
    int count = 0;
    printf("请输入一个大于1的整数：\n");
    scanf("%d", &i);
    for (m = 1; m <= i; m++) {
        if (i % m == 0) // 统计要判断的数的因数个数
            count++;
    }
    if (count == 2) // 如果只有2个因数，则为素数
        printf("%d是素数\n", i);
    else
        printf("%d不是素数\n", i);
    return 0;
}

这种方法虽然直观易懂，但是效率较低，尤其是对于较大的数值时性能不佳[^1]。

#### 方法二：优化后的遍历算法
考虑到任何合数至少有一个不大于它平方根的小质因数，因此只需检查从2至目标数平方根范围内的整除情况即可。一旦发现能被某个数整除就立即返回非素数的结果；反之，在完成循环后仍未找到可整除者，则确认为目标数为素数。

#include <stdio.h>
#include <math.h>

int is_prime(int n){
    if(n<=1)return 0;
    for(int i=2;i<=sqrt((double)n);++i){
        if(n%i==0)return 0;
    }
    return 1;
}

int main(){
    int num;
    printf("输入一个整数:");
    scanf("%d",&num);

    if(is_prime(num))
        printf("%d 是素数。\n",num);
    else
        printf("%d 不是素数。\n",num);

    return 0;
}

这段代码利用了`<math.h>`库中的`sqrt()`函数来获取给定数的最大潜在因数边界，并以此为基础构建更高效的测试流程[^3]。

#### 方法三：简化版逻辑判定
另一种较为简洁的方式是在遇到第一个能够整除当前待测数的情况时立刻终止运算并给出结论。这种方式同样基于上述提到的原则—只要存在一个小于此数一半大小且可以将其完全分割成两部分的自然数，那么这个数肯定不是素数。

#include <stdio.h>

int main() {
    int i = 0;
    int j = 0;

    scanf("%d", &j);

    for(i = 2; i <= j / 2; ++i) {
        if(j % i == 0) {
            printf("这不是素数\n");
            break;
        }
    }

    if(i > j / 2 && j != 1)
        printf("这是素数\n");

    return 0;
}

这里采用了一个简单的for循环结构来进行逐次尝试性的除法操作，当检测到任意一次成功整除事件发生之后便停止进一步探索，并输出相应的提示信息[^2]。

输入一个大于3的整数n 判定他是否为素数 用c语言

在C语言中，判断一个大于3的整数是否为素数通常采用试除法，即从2到这个数的平方根范围内，看是否有能整除它的数。如果存在这样的数，那么它就不是素数；如果没有找到，就是素数。以下是简单的C程序实现：

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) {
        return false; // 小于等于1的数不是素数
    } else if (n == 2) {
        return true; // 2是最小的素数
    } else if (n % 2 == 0) {
        return false; // 偶数除了2之外都不是素数
    }
    int sqrt_n = sqrt(n); // 只需要检查到√n
    for (int i = 3; i <= sqrt_n; i += 2) { // 从3开始，每次增加2，跳过偶数
        if (n % i == 0) {
            return false;
        }
    }
    return true; // 没有找到因子，所以是素数
}

int main() {
    int n;
    printf("请输入一个大于3的整数：");
    scanf("%d", &n);

    if (isPrime(n)) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }

    return 0;
}