文档章节

使用c语言完成了一个求素数的程序

RenKaidi
 RenKaidi
发布于 2015/07/16 08:58
字数 1213
阅读 19
收藏 0

有题目要求完成一款求素数的程序,由于之前有思考过这个问题,所有轻车熟路直奔向减少不必要计算的方向.很遗憾,我在此程序中使用了一次”go to”.并且由于我个人编程技术的不完美,致使难以在保证优雅性的前提下完成”自增优化”.

求千万内素数不挂.(精度嘛,知识所限,不清楚)

// 15pb_c_.0.13_求素数.cpp : 定义控制台应用程序的入口点。
//求素数0.1版本
//2015-3-13 17:42:51
/*/通过对自建素数表格的检索判定,是否是合数.减少了判断次数. //新版本改进思路:取掉goto. //任Kitty //0.2版本 //计划减少一半的判断:一个数字如果在小于等于它的平方根的整数里没有发现它是一个合数,那么它是一个质数.结果非常惊喜,求十万以内速度提高了百分之七百多.666 //个位数是[2,4,5,6,8,0]的数字必然是合数.当然2除外. //方法是:自增运算改为只能生成[1,3,7,9]序列的运算即可3(+4,+2,+2,+2,)循环.我只做了+2的处理,也就是加5次2.求十万以内速度提高了零点几毫秒. //被3整除的情况也是一个问题,因为每隔几个数字就会出现它.是否能有效解决它呢? //2015年3月14日 17:11:38 // //0.3版本 //该申请多少栈内存比较合适呢?素数占整数的比例是什么关系呢? //如果不是动态的更进,暂用"xianzhi数"的二分之一申请.这也防止了太小的数字导致.当xianzhi=100的时候,质数小于四分之一. //当求十万以内质数的时候,比例为1:10.425参考这个:(http://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8%E5%AE%9A%E7%90%86)素数定理 //如果是在栈上,默认情况下栈溢出在申请25万到30万个int数组的时候.改成malloc.在1:10的节约比例下,申请一千万int构成数组不报错,用时10s. //其实如果结果不做保存而是循环打印的时候,只需要申请比例数组后的一半的数组来保存用来判断的质数. //2015年3月15日 09:36:21 */

#include "stdafx.h"
#include <string>
#include <iostream>
#include "time.h"
#include <Windows.h>//计时器使用

#define xianzhi 10000000//达到千万?依照我现有的知识精度无法验证.



int _tmain(int argc, _TCHAR* argv[])
{

    int i限制比例=2;
    if (xianzhi>=100000)
    {i限制比例=10;};

    int i理论所占=xianzhi/i限制比例;

    int* c素数=NULL;
    c素数=(int*)calloc(i理论所占,sizeof(int));//申请存储素数的动态数组

    //申请失败,calloc返回空指针的时候
    if(c素数==0)
    {
        printf_s("你要求的数字太大?还是你内存太小?还是你要求的数字范围有问题?");
        return 2;
    }

    //int c素数[i理论所占];//未来素数构成的数组
    int i数组索引=1;//为将要加入素数的数组索引
    int i正在检测=3;//正在检测的数字



    //计时开始
    LARGE_INTEGER  large_interger;  
    double dJishi;  
    __int64  iTimec1, iTimec2;  
    QueryPerformanceFrequency(&large_interger);  
    dJishi = large_interger.QuadPart;  
    QueryPerformanceCounter(&large_interger);  
    iTimec1 = large_interger.QuadPart;  
    //计时部分 


    //为cSushu初始化//更好的初始化方式是memset:
    //memset(&c素数,0, sizeof(int)*i理论所占);


    c素数[0]=2;//初始化初始位

    for(;i正在检测<=xianzhi;i正在检测++)//默认从3开始检测,这里应当[+4,+2,+2,+2],我只做了相当于5次+2,相当于多做了25%的无用功.还会有0.3吗?
    {
        for(int i寻找索引=0;i寻找索引<i数组索引;i寻找索引++)//寻找索引
        {

            if(i正在检测%c素数[i寻找索引]==0)
            {goto 合数;};//条件成立表示,这是合数.

            if(c素数[i寻找索引]>=(int)sqrt(i正在检测))
            {break;};//条件成立表示,这是一个质数,不需要进一步的判断.这里可以使用==,因为上面的if检测防止了待检查数字是当前索引到的质数的平方的情况.
        };
        //存储
        c素数[i数组索引]=i正在检测;
        i数组索引++;

合数:;//跳出
    };

    //计时结束
    QueryPerformanceCounter(&large_interger);  
    iTimec2 = large_interger.QuadPart;  
    printf("本机高精度计时器频率%lf\n", dJishi);  
    printf("第一次计时器值%I64d 第二次计时器值%I64d \n计时器差%I64d\n", iTimec1, iTimec2, iTimec2 - iTimec1);  
    printf("计时%lf毫秒\n", (iTimec2 - iTimec1) * 1000 / dJishi);  
    //结束部分



    for(int i=0;i<=(i数组索引-1);i++)
    {
        printf_s("%i %d\n",i+1,c素数[i]);
    }

    free(c素数);  

    return 0;
};

算法优化让我尝到了甜头.

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

© 著作权归作者所有

RenKaidi
粉丝 5
博文 9
码字总数 5103
作品 0
其他
程序员
私信 提问
小蚂蚁学习C语言(14)——C语言函数(下)

先上一个例子,使用自定义函数,判断一个指定范围的数字是否是素数,如果是素数就输出,这么一个小程序。 /* 求1到某个数值所有的素数 学php的小蚂蚁*/ include <stdio.h> /* 判断一个数字是...

嗜学如命的小蚂蚁
2015/12/10
67
0
C语言/C++程序设计编程基础学习—经典算法

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/24
0
0
Apocalypse/c2go

用go实现《c语言经典算法》中的100个例子 腻了,就此终结。 目 录 1.有一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的...

Apocalypse
2015/03/29
0
0
在C语言中求素数的算法

在C语言中求素数为什么是用一个数分别去除2到sqrt(这个数) 那个sqrt(这个数)怎么来的? 求高手解答~~~·

csp
2012/05/08
5.6K
8
LoadRunner脚本编写之二

今天有朋友问我,关于loadrunner脚本编第二篇什么时候写,我告诉他都没什么东西了。要学习一门语言,基本的语法和思想很重要。现在每个人都识字,那是不是每个识字的人都可以当作家。不可能,...

长平狐
2013/03/12
71
0

没有更多内容

加载失败,请刷新页面

加载更多

好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0
浅谈java过滤器Filter

一、简介 Servlet中的过滤器Filter是实现了javax.servlet.Filter接口的服务器端程序,主要的用途是过滤字符编码、做一些业务逻辑判断如是否有权限访问页面等。其工作原理是,只要你在web.xml...

青衣霓裳
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部