利用数组求前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]);
    }
}

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

这个是没有优化的结果:

技术分享

这个是优化之后的结果:
技术分享

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。