質(zhì)數(shù)：質(zhì)數(shù)又稱(chēng)素?cái)?shù)。一個(gè)大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；否則稱(chēng)為合數(shù)。

問(wèn)題一：給定一個(gè)整數(shù)N，找出小于N的質(zhì)數(shù)，從小到大打印出來(lái)
思路：
1、試除法
試除法就是不斷地嘗試能否整除。比如要判斷自然數(shù) x 是否質(zhì)數(shù)，就不斷嘗試小于 x 且大于1的自然數(shù)，只要有一個(gè)能整除，則 x 是合數(shù)；否則，x 是質(zhì)數(shù)。
試除法的關(guān)鍵就是如何減少試除的次數(shù)，需要考慮幾個(gè)點(diǎn)：
一是除了2之外，其余的質(zhì)數(shù)只可能是奇數(shù)
二是對(duì)于一個(gè)數(shù)而言，其因數(shù)一定是成對(duì)出現(xiàn)的，其中一個(gè)因數(shù)大于該數(shù)的平方根，另一個(gè)因數(shù)小于該數(shù)的平方根，因此試除的次數(shù)只要從2遍歷到該數(shù)的平方根加1即可（加1是因?yàn)榭紤]到開(kāi)方后是小數(shù)，主要是3這個(gè)邊界情況）。
2、篩選法
首先，2是公認(rèn)最小的質(zhì)數(shù)，所以，先把所有2的倍數(shù)去掉；然后剩下的那些大于2的數(shù)里面，最小的是3，所以3也是質(zhì)數(shù)；然后把所有3的倍數(shù)都去掉，剩下的那些大于3的數(shù)里面，最小的是5，所以5也是質(zhì)數(shù)……
上述過(guò)程不斷重復(fù)，就可以把某個(gè)范圍內(nèi)的合數(shù)全都除去（就像被篩子篩掉一樣），剩下的就是質(zhì)數(shù)了。

/方法一：試除法
void find_prime_1(int num)
{
    int* prime = (int*)malloc(sizeof(int) * num);
    if(num < 2)
    {
        printf("輸入數(shù)據(jù)有誤，質(zhì)數(shù)至少要大于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");
}

篩選法的時(shí)間復(fù)雜度要遠(yuǎn)低于試除法，當(dāng)輸入的數(shù)字是1000000時(shí)，試除法的運(yùn)行時(shí)間為14.526s，而篩選法的運(yùn)行時(shí)間僅為8.696s

問(wèn)題二：給定一個(gè)整數(shù)N，找出自然數(shù)中最小的N個(gè)質(zhì)數(shù)，從小到大打印出來(lái)
算法思路：設(shè)計(jì)一個(gè)計(jì)數(shù)變量來(lái)控制程序運(yùn)行是否結(jié)束，該計(jì)數(shù)變量用于存儲(chǔ)已經(jīng)找出的質(zhì)數(shù)的個(gè)數(shù)，此外還需要設(shè)計(jì)一個(gè)函數(shù)用于判斷一個(gè)數(shù)是否是質(zhì)數(shù)

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;
        }
    }
}

/*給定一個(gè)整數(shù)N，找出自然數(shù)中最小的N個(gè)質(zhì)數(shù)，從小到大打印出來(lái)*/
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");

}

問(wèn)題3：給定一個(gè)數(shù)，求出它的所有質(zhì)數(shù)因子，例如180 = 2 * 2 * 3 * 3 * 5
算法思路：一個(gè)數(shù)的因數(shù)，除了質(zhì)數(shù)之外，其余的數(shù)均還存在因數(shù)，可以通過(guò)前面已經(jīng)找到的質(zhì)數(shù)因子排除掉能被質(zhì)數(shù)因子整除的其他因子

/*給定一個(gè)數(shù)，求出它的所有質(zhì)數(shù)因子，例如180 = 2 * 2 * 3 * 3 * 5*/
void find_prime_gradient(int num)
{
    int i = 0;
    for(i = 2; i <= num; i++)  //邊界情況，輸入值就是一個(gè)質(zhì)數(shù)本身，那么輸出就是它本身
    {
        while(num % i == 0)
        {
            printf("%d ", i);
            num = num / i;  //排除掉后面存在能被i整除的非質(zhì)數(shù)因子
        }
    }
}