文档章节

利用数组求前n个质数

陈洪波
 陈洪波
发布于 2015/05/19 19:34
字数 809
阅读 15
收藏 1

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

#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]);
    }
}

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

这个是没有优化的结果:

这里写图片描述

这个是优化之后的结果:
这里写图片描述

本文转载自:http://blog.csdn.net/hongbochen1223/article/details/45105975

陈洪波
粉丝 2
博文 76
码字总数 1552
作品 0
济南
程序员
私信 提问
LeetCode:Count Primes - 统计质数数量

1、题目名称 Count Primes(统计质数数量) 2、题目地址 https://leetcode.com/problems/count-primes/ 3、题目内容 英文:Count the number of prime numbers less than a non-negative nu......

北风其凉
2015/09/06
851
0
从数组到HashMap之算法解释

作者:Xcafe 编辑日期:20161228 博客:https://my.oschina.net/xcafe 一 数组是什么?   忘了在哪本书里曾看到过类似这样的一句话“所有的数据结构都是数组的演化”,想想其实是有道理的...

Xcafe
2016/12/29
4.1K
22
学习:数学----欧拉定理与扩展欧拉定理

欧拉定理和扩展欧拉定理可以解决形如5100000000000000000000等大数幂取模或者求ax mod n=1的大于1的最小x值等一类问题,其中欧拉函数占巨大的重要性,有效的将复杂的大数幂取模问题转化为简单...

七月流
04/30
0
0
每周一课:L12 Euclidean algorithm(12.2)

P12.2 CommonPrimeDivisors Check whether two numbers have the same prime divisors. P12.2 质因子数 判断两个数是否有相同的因子个数 大于1的自然数中,除了1和它本身以外不再有其他因数的...

AiFan
02/17
0
0
java-生成无重随机序列-10x速~

最近需要做个无重随机序列,在网上找了半天,找到一个还是效率不高,后来我想了算法思路——完全剩余系,自己忙里抽空自己写了一个。后来发现效率还可以,特发出来请大家指点一下~ import ja...

alvinte
2013/03/01
2.6K
2

没有更多内容

加载失败,请刷新页面

加载更多

100天搞定机器学习|Day55 最大熵模型

1、熵的定义 熵最早是一个物理学概念,由克劳修斯于1854年提出,它是描述事物无序性的参数,跟热力学第二定律的宏观方向性有关:在不加外力的情况下,总是往混乱状态改变。熵增是宇宙的基本定...

机器学习算法与Python实战
32分钟前
5
0
找子表

select a.constraint_name, a.table_name, b.constraint_name from user_constraints a, user_constraints b where a.constraint_type = 'R' and b.constraint_type = 'P' and a.r_constrain......

兵荒马乱的青春
34分钟前
6
0
Web应用安全如何防御或者检查漏洞?

     Web应用安全如何防御或者检查漏洞?这是大家一直关心的问题。随着计算机技术的发展,网络漏洞也变得越来越多样化了,你知道吗,每隔9 小时就会发布 1 个严重漏洞,并且有可能会进行远...

梅丽莎好
42分钟前
7
0
Vim 复制粘帖格式错乱问题的解决办法

有时候,复制文本(尤其是代码)到 Vim,会出现格式错乱的问题。看样子,应该是自动缩进惹得祸。本文不去深究原因,直接给出解决方法。 1. paste 模式 运行如下命令,进入 paste 模式: :set...

观海562
43分钟前
7
0
OSM初识(三)OSM Data

一 导出数据 将XML格式的OSM数据转换成另一种格式。 二 提取数据 剪切你选择区域内的数据,或者提取出特定区域特定的特征 三 数据格式 OSM文件仅属于OSM,不能用别的软件打开。其中后缀为bz2...

yuankaichao
52分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部