有关质数的一些算法及C语言实现

质数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

问题一：给定一个整数N，找出小于N的质数，从小到大打印出来
思路：
1、试除法
试除法就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。
试除法的关键就是如何减少试除的次数，需要考虑几个点：
一是除了2之外，其余的质数只可能是奇数
二是对于一个数而言，其因数一定是成对出现的，其中一个因数大于该数的平方根，另一个因数小于该数的平方根，因此试除的次数只要从2遍历到该数的平方根加1即可（加1是因为考虑到开方后是小数，主要是3这个边界情况）。
2、筛选法
首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……
上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

/方法一：试除法
void find_prime_1(int num)
{
    int* prime = (int*)malloc(sizeof(int) * num);
    if(num < 2)
    {
        printf("输入数据有误，质数至少要大于1！\n");
        return;
    }
    int i = 0, j = 0, k = 0;
    if(num == 2)
    {
        printf("%d", num);
    }
    else
    {
        prime[k++] = 2;
        for(i = 3; i <= num; i++)
        {
            //printf("sqrt = %d", (int)sqrt(i)+1);
            if(i % 2 == 0)
                continue;
            for(j = 2; j <= (int)sqrt(i) + 1; j++)
            {
                if(i % j == 0)
                    break;

                if(j == (int)sqrt(i) + 1)
                    prime[k++] = i;
            }
        }
    }

    for(i = 0; i < k; i++)
    {
        printf("%d ", prime[i]);
    }
    printf("\n");

}

//方法二：筛选法
void find_prime_2(int num)
{
    int* prime = (int*)malloc(sizeof(int) * (num + 1));
    //memset(prime, 1, sizeof(prime));
    int i = 0, j = 0;
    //printf("length = %d\n", sizeof(prime) / sizeof(int));
    for(i = 0; i < num + 1; i++)
    {
        if(i < 2)
            prime[i] = 0;
        else
            prime[i] = 1;
    }

    for(i = 2; i < num + 1; i++)
    {
        if(prime[i])
        {
            printf("%d ", i);
            for(j = i + i; j < num + 1;j = j + i)
            {
                prime[j] = 0;
            }
        }

    }

    printf("\n");
}

筛选法的时间复杂度要远低于试除法，当输入的数字是1000000时，试除法的运行时间为14.526s，而筛选法的运行时间仅为8.696s

问题二：给定一个整数N，找出自然数中最小的N个质数，从小到大打印出来
算法思路：设计一个计数变量来控制程序运行是否结束，该计数变量用于存储已经找出的质数的个数，此外还需要设计一个函数用于判断一个数是否是质数

int isprime(int num)
{
    int i = 0;

    if(num < 2)
        return 0;

    if(num == 2)
        return 1;
    else
    {
        for(i = 2; i <= (int)sqrt(num) + 1; i++)
        {
            if(num % i == 0)
                return 0;

            if(i == (int)sqrt(num) + 1)
                return 1;
        }
    }
}

/*给定一个整数N，找出自然数中最小的N个质数，从小到大打印出来*/
void find_prime_3(int num)
{
    int count = 0;
    int i = 0;
    for(i = 2; ; i++)
    {
        if(isprime(i))
        {
            count++;
            if(count > num)
                break;
            else
                printf("%d ", i);
        }
    }
    printf("\n");

}

问题3：给定一个数，求出它的所有质数因子，例如180 = 2 * 2 * 3 * 3 * 5
算法思路：一个数的因数，除了质数之外，其余的数均还存在因数，可以通过前面已经找到的质数因子排除掉能被质数因子整除的其他因子

/*给定一个数，求出它的所有质数因子，例如180 = 2 * 2 * 3 * 3 * 5*/
void find_prime_gradient(int num)
{
    int i = 0;
    for(i = 2; i <= num; i++)  //边界情况，输入值就是一个质数本身，那么输出就是它本身
    {
        while(num % i == 0)
        {
            printf("%d ", i);
            num = num / i;  //排除掉后面存在能被i整除的非质数因子
        }
    }
}