C语言实现判断一个数是否为素数并求100以内的所有素数

判断一个数是否为素数

算法思想

设一个正整数x，sqrt(x)为x开平方后的值，若x不为素数，则x=a*b，a,b为2~x-1之间的整数，且当2=< a <= sqrt(x)时，必有sqrt(x)=< b <= x-1，即a和b必有一个数在2~sqrt(x)范围内，反推之，若x不可被2~sqrt(x)范围内的任何整数整除，则x必为素数。

代码实现

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x;
    scanf("%d", &x);
    printf("%d是否为素数: %d", x, IsPrime(x));
    return 0;
}

int IsPrime(int x)
{
    int i, squareRoot;
    //小于或等于1的整数均不为素数，预先排除
    if(x <= 1) return 0;
    //sqrt(x)为开平方函数，其返回结果为浮点数，通过类型强转获得小于该浮点数的最大整数
    squareRoot = (int)sqrt(x);
    for(int i = 2;i <= squareRoot;i++)
    {
        //通过取余函数，若除得余数为0，说明x可被i整除，x不为素数
        if(x%i == 0) return 0;
    }
    return 1;
}

求100以内的所有素数

算法思想

若一个正整数x不为素数，则它必定可以由两个或两个以上的素数的乘积表示，并且这几个素数中必定有一个素数小于或等于sqrt(x)，即x必定可以被2~sqrt(x)中的一个素数整除。设一个数组int a[101];，使a[2]=2，a[3]=3，.....，a[100]=100，排除此数组中所有可以被2~sqrt(100)中的素数整除的数（素数本身除外），则剩下的元素数则均为素数。那么如何求2~sqrt(100)中的素数呢，很简单，不用求，首先从最小的素数2开始，将3~100中可以被2整除的数组元素置为0，然后往下循环，下一个不为0的数组元素必定为素数，一直循环至下一个不为0的数组元素大于sqrt(100)时，数组中可以被2~sqrt(100)中的素数整除的数均被置为0了，则数组中剩下不为0的数均为素数

代码实现

#include <stdio.h>
#include <stdlib.h>
#define N 100

int main()
{
    int a[N+1];
    SiftPrime(a, N);
    PrintPrime(a, N);
    return 0;
}

void SiftPrime(int a[], int n)
{
    //初始化数组元素
    for(int i = 2;i <= n;i++)
    {
        a[i]=i;
    }
    for(int i = 2;i <= sqrt(n);i++)
    {
        //当a[i]不为0时，必定为素数
        if(a[i] != 0)
        {
            //将a[i]之后所有不为0的数除以a[i]求余，若可整除，则不为素数，置为0
            for(int j = i+1;j <= n;j++)
            {
                if(a[j] != 0 && a[j]%a[i] == 0)
                    a[j] = 0;
            }
        }
    }
}

void PrintPrime(int a[], int n)
{
    for(int i = 2;i < n;i++)
    {
        if(a[i] != 0)
        printf("%d\t", a[i]);
    }
}