首页 > 代码库 > C语言求质数的算法

C语言求质数的算法

前言

上次被出了一题质数的C语言求解题目(面试),当时用了最粗暴的算法,回来仔细参考资料,其实答案有很多种:

1,小学生版本:

判断 x 是否为质数,就从 2 一直算到 x-1。
static rt_uint32_t array1[ARRAY_LEN];
void func1(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array1[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 2; x <= ARRAY_LEN; x++)
    {
        y = 0;
        for (i = 1; i <= x; i++)
        {
            if (x % i == 0)
            {
                y++;
            }
        }
        if (y == 2)
        {
            z++;
            array1[x - 1] = x;
        }
    }
    array1[0] = 1;
}

2,小学生毕业版:

x 如果有质因数,肯定会小于等于 x/2,所以捏,就从 2 一直到 x/2 即可。
static rt_uint32_t array2[ARRAY_LEN];
void func2(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array2[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 3; x <= ARRAY_LEN; x++)
    {
        y = 0;
        for (i = 2; i <= x / 2; i++)
        {
            if (x % i == 0)
            {
                y++;
                break;
            }
        }
        if (y == 0)
        {
            z++;
            array2[x - 1] = x;
        }
    }
    array2[0] = 1;
    array2[1] = 2;
}

3,初中生版:

除了2以外的质因数都是奇数。所以算从3开始一直到 x/2 的所有奇数。
static rt_uint32_t array3[ARRAY_LEN];
void func3(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array3[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 3; x <= ARRAY_LEN; x += 2)
    {
        y = 0;
        for (i = 2; i <= x / 2; i++)
        {
            if (x % i == 0)
            {
                y++;
                break;
            }
        }
        if (y == 0)
        {
            z++;
            array3[x - 1] = x;
        }
    }
    array3[0] = 1;
    array3[1] = 2;
}

4,高中生版:

其实只要从 2 一直尝试到根号x,就可以了。因为x只要有因数必定有一个因数小于等于根号x。
static rt_uint32_t array4[ARRAY_LEN];
void func4(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array4[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 3; x <= ARRAY_LEN; x++)
    {
        y = 0;
        for (i = 2; i <= sqrt(x); i++)
        {
            if (x % i == 0)
            {
                y++;
                break;
            }
        }
        if (y == 0)
        {
            z++;
            array4[x - 1] = x;
        }
    }
    array4[0] = 1;
    array4[1] = 2;
}

5,本科生版:

把上面的版本都综合起来
static rt_uint32_t array5[ARRAY_LEN];
void func5(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array5[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 3; x <= ARRAY_LEN; x += 2)
    {
        y = 0;
        for (i = 2; i <= sqrt(x); i++)
        {
            if (x % i == 0)
            {
                y++;
                break;
            }
        }
        if (y == 0)
        {
            z++;
            array5[x - 1] = x;
        }
    }
    array5[0] = 1;
    array5[1] = 2;
}

6,本科生毕业版本:

就是当i是质(素)数的时候,i的所有的倍数必然是合数。如果i已经被判断不是质数了,那么再找到i后面的质数来把这个质
数的倍数筛掉。
static rt_uint32_t array6[ARRAY_LEN];
void func6(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i += 2)
    {
        array6[i - 1] = i;
    }

    for (rt_uint32_t i = 3; i < sqrt(ARRAY_LEN); i+=2)
    {
        if (array6[i-1])
        {
            for(rt_uint32_t j=i<<2;j<=ARRAY_LEN;j+=i)
            {
                array6[j] = 0;
            }
        }
    }
    array6[1] = 2;
}

总结

分析了6个算法在我的嵌入式平台运行结果:
定义ARRAY_LEN = 1000;    
func12513922
func2221563
func3213926
func4762945
func5674993
func614663
我们可以看到func4、func5并没有我们想象的那么节省时间,我想问题主要出在sqrt上面;sqrt本身是比较耗时的计算,然后func4与func5调用sqrt的次数又比较多;所以导致结果不太乐观。当然如果把ARRAY_LEN调大,可能结果又会不一样

至此,也就只是我本科毕业的水准了,后面还有更好的纯C算法可以告诉我。