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

問題一：給定一個(gè)整數(shù)N庄萎，找出小于N的質(zhì)數(shù)，從小到大打印出來
思路：
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)榭紤]到開方后是小數(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ù)……
上述過程不斷重復(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

問題二：給定一個(gè)整數(shù)N，找出自然數(shù)中最小的N個(gè)質(zhì)數(shù)屯吊，從小到大打印出來
算法思路：設(shè)計(jì)一個(gè)計(jì)數(shù)變量來控制程序運(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ù)骗爆，從小到大打印出來*/
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：給定一個(gè)數(shù)，求出它的所有質(zhì)數(shù)因子蔽介，例如180 = 2 * 2 * 3 * 3 * 5
算法思路：一個(gè)數(shù)的因數(shù)摘投，除了質(zhì)數(shù)之外，其余的數(shù)均還存在因數(shù)虹蓄，可以通過前面已經(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ù)因子
        }
    }
}