注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

始めの一歩

不是世界变得无聊了,而是你变成了无聊的人……

 
 
 

日志

 
 

【C++】源码 1 -- Eratosthenes 算法 求 素数  

2012-09-30 19:12:33|  分类: FateのC/C++の源 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

考研改了专业课,无奈只能再次自学了 C++,遇到一题:用 Eratosthenes 算法求素数,特编写此程序,聊以备份……

附上源码:(初出茅庐,难免有写的不好的地方,仅作备份之用,欢迎指点,喷子退散……)

/************************************************************
             Eratosthenes 算法 求 素数

算法如下:

1、首先保留 2,然后把 2 的倍数从中去掉;
2、再保留 3,然后把 3 的倍数从中去掉;
3、以此类推……

************************************************************/

#include <iostream.h>
#include <malloc.h>          // 声明 new() 函数的头文件,用于「动态分配内存」
#include <iomanip.h>        // 声明 setw() 函数的头文件,用于「格式化输出」

#define MAXSIZE 1000      // 找出 0 - MAXSIZE 中的素数

typedef struct Node {        // 线性单链表结点结构
    int num;
    struct Node *next;
}Node, *NodePtr;

void Init_List(NodePtr &L, int n);     // 初始化链表,分配初始数据
void Test_List(NodePtr L, int n);      // 输出链表数据,测试是否正确建立了链表(该函数用于调试)
void Eratosthenes(NodePtr &L);     // 用 Eratosthenes 算法去掉链表 L 中的非素数
void Printf_Prime(NodePtr L);         // 输出链表 L 中的素数

void main (void)
{
    NodePtr L = NULL;
    Init_List(L, MAXSIZE);       // 初始化数据
//  Test_List(L, MAXSIZE);

    NodePtr Head = L;
    Eratosthenes(L);              // 去掉非素数

    Printf_Prime(Head);         // 输出素数
}

void Init_List(NodePtr &L, int n) {        // 初始化链表,分配初始数据
    L = (NodePtr)new(Node);
    L->next = NULL;                  // 建立头结点,头结点不含数据
    NodePtr p = NULL, q = L;
    for (int i=1; i<=n; i++) {        // 用 n 作为数据规模,生成线性单链表
        p = (NodePtr)new(Node);
        p->num = i;                      // 输入结点数据 1 - n
        q->next = p;
        q = q->next;
    }
    p->next = NULL;
}

void Test_List(NodePtr L, int n) {        // 输出链表数据,测试是否正确建立了链表(该函数用于调试)
    L = L->next;
    for (int i=0; i<n; i++) {
        cout<<L->num<<' ';
        L = L->next;
    }
    cout<<endl;
}

void Eratosthenes(NodePtr &L) {        // Eratosthenes 算法本体

    L = L->next->next;           // 去掉头结点,数字 1,从数字 2 开始
    NodePtr p = L->next;       // p,q 用于确定当前数据的位置,实现删除操作
    NodePtr q = L;
    int m, n;               // m,n 对应结点的数据,用于判断某结点与另一结点的倍数关系
    while (L->next != NULL) {
        while (p->next != NULL) {
            m = L->num;
            n = p->num;
            if (n%m != 0) {          // 如果不是倍数关系,那么指针都后移,为下一个循环做准备
                p = p->next;
                q = q->next;
            }
            else {           // 如果是倍数关系(即:结点为非素数),那么删除结点,重构链表关系
                q->next = p->next;
                free(p);         // 删除结点时,释放空间
                p = q->next;
            }
        }
        if ((p->next == NULL) && (p->num % L->num == 0)) {       // 循环的收尾处理
            q->next = NULL;
            free(p);
        }
        L = L->next;
        p = L->next;
        q = L;
    }
}

void Printf_Prime(NodePtr L) {       // 输出链表 L 中的素数
    L = L->next->next;
    int count = 0;
    while (L->next != NULL) {
        cout<<setw(5)<<L->num;
        L = L->next;
        count++;
    }
    cout<<setw(5)<<L->num<<endl<<endl;
    cout<<"The number of Prime Number: "<<++count<<endl<<endl;
}

 

程序结果:

【C++】源码 1 -- Eratosthenes 算法 求「素数」 - 灼眼のFate - 運命の始まり

  评论这张
 
阅读(173)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018