c语言 判断一个数是否为素数

根据初等数论,一个整数不能整除他的平方数之内的整数就是素数..

比较简单的方法：

#include <stdio.h>

int main(int argc, char *argv[])
{
    int n,r,i;
    scanf("%d",&n);

    for(i = 2; i < n; i++)
    {
        r = n % i;
        if(r == 0)
            break;
     }

    if(i >= n)
        printf("yes\n");
    else
        printf("no\n");

    return 0;
}

以上这种方法比较容易理解，但是需要的时间比较长，因为系统要将所有的数字进行比较运算，而实际上我们可以将偶数去掉，甚至我们只需要循环到到根号下N+1就够了。

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

#define YES 1
#define NO 0

int isprime(int num)
{
    int i, j;

    if (num == 2)
        return YES;
    else if (num < 2 || num % 2 == 0)
        return NO;
    else
    {
        j = (int)sqrt(num + 1);
        for (i = 3; i <= j; i = i + 2)
            if (num % i == 0)
                return NO;
    }

    return YES;
}

int main(int argc, char *argv[])
{
    int N;
    scanf("%d", &N);

    if (isprime(N) == YES)
        printf("yes\n");
    else
        printf("no\n");

    return 0;
}