首页 / 操作系统 / Linux / C语言求素数（质数）的算法

前言上次被出了一题质数的C语言求解题目（ http://www.linuxidc.com/Linux/2014-06/103097.htm ），当时用了最粗暴的算法，回来仔细参考资料，其实答案有很多种：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;
}更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2014-06/103100p2.htm