利用数组求前n个质数

我的算法思想和实现方式都在代码和注释当中呢，这样的方式确实使算法复杂度降低一个等级，很好啊。

#include <stdio.h>
#include <time.h>

/**
 * 利用数组求前n个质数
 * 确定一个数m是否为质数，可以用已求出的质数对m
 * 的整除性来确定
 */

//如果不知道质数的特性和想不到优化思路的方法
void getNPrimes_normal();

//优化之后的方法
void getNPrimes_optimize();

int main(void)
{
    clock_t start,end;

    start = clock(); //开始时，取得开始时间。

    //通常的做法的运行时间，输入的n=10000
    //getNPrimes_normal();

    //优化后的运行时间
    getNPrimes_optimize();

    end = clock();   //结束时，取得结束时间

    printf("Run time: %lf S",(double)(end-start)/CLOCKS_PER_SEC);

    return 0;
}

//通常用到的想法
void getNPrimes_normal(){
    /**
     * 用于保存质数的数量
     * @brief count
     */
    int count;
    printf("Please the count of prime number:\n");

    scanf("%d",&count);

    //使用数组来保存所求出的质数
    int primes[count];

    /**
     * 首先，第一个已知的质数是2，
     * 则计算应该从3开始
     */
    primes[0] = 2;
    int pc = 1;

    int m = 3; //从数字3开始

    while(pc < count){

        int k = 0;

        // 这里只要找不到质数，就会一直在这个循环中
        while(k < pc){
            if(m % primes[k] == 0){
                m += 1;
                k = 0;
            }else{
                k++;
            }
        }

        //找到质数之后，跳出上面的循环
        //这个的执行是先执行primes[pc] = m;
        //再去执行pc++;
        primes[pc++] = m;
        m+=1;
    }

    /**
     * 对质数进行输出操作
     *
     */
    for(pc = 0;pc < count;pc++){
        printf("%4d\t",primes[pc]);
    }

}


//优化之后的方法
void getNPrimes_optimize(){
    /**
     * 用于保存质数的数量
     * @brief count
     */
    int count;
    printf("Please the count of prime number:\n");

    scanf("%d",&count);

    //使用数组来保存所求出的质数
    int primes[count];

    /**
     * 首先，第一个已知的质数是2，
     * 则计算应该从3开始
     */
    primes[0] = 2;
    int pc = 1;

    int m =3; //从数字3开始

    while(pc < count){

        /**
         * 首先需要解决的是如何判断一个数是一个质数
         * 1：除了数字2之外，其他所有的质数都是奇数
         * 2：假设某一个数字是k，只要判断k能否被k之前
         *    的质数整除就可以了，如果能够整除，则k就是
         *    合数，如果不能整除，k就是质数
         *
         *    但是，为了减少算法的复杂度，我们这样设想
         *    p*q=k
         *    则肯定p和q中：
         *    p*p <=k的话，q*q >= k
         *    则，只要求k能否被k的平方根之前的数字整除就可以了。
         *
         *    基于这个思想，我们的实现方式如下：
         */

        int k = 0;

        // 这里只要找不到质数，就会一直在这个循环中
        while(primes[k] * primes[k] <= m){
            if(m % primes[k] == 0){
                m += 2; //除了数字2之外，其他所有的质数都是奇数
                k = 1; //不用使用数字2去测试
            }else{
                k++;
            }
        }

        //找到质数之后，跳出上面的循环
        //这个的执行是先执行primes[pc] = m;
        //再去执行pc++;
        primes[pc++] = m;
        m+=2;
    }

    /**
     * 对质数进行输出操作
     *
     */
    for(pc = 0;pc < count;pc++){
        printf("%4d\t",primes[pc]);
    }
}

下面是我的运行结果，第一个是没有优化的结果，第二个是经过算法优化后的结果，效果还是很明显的。

这个是没有优化的结果：

这个是优化之后的结果：

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>

版权声明：本文为博主原创文章，未经博主允许不得转载。