| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3245 人关注过本帖
标题:關於素數的一些例子
只看楼主 加入收藏
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
结帖率:100%
收藏
 问题点数:0 回复次数:12 
關於素數的一些例子
程序代码:
#include <cstdio>
#include <cstdlib>
#include <conio.h>

void Pause(void)
{
    printf_s("\nPress any key to continue...");
    _getch();
}

bool IsPrime(unsigned short n)
{
    if (n < 2)
    {
        return false;
    }

    if (n % 2 == 0)
    {
        return n == 2;
    }
    if (n % 3 == 0)
    {
        return n == 3;
    }
    if (n % 5 == 0)
    {
        return n == 5;
    }

    for (unsigned short i = 7; i * i <= n; i += 2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

const size_t NUMBER_PER_ROW = 5;

int main(void)
{
    size_t index = 0;

    /* 輸出100-200之間的素數 */
    for (unsigned short x = 100; x <= 200; ++x)
    {
        if (IsPrime(x))
        {
            printf_s("%4u", x);
            putchar((++index % NUMBER_PER_ROW == 0) ? '\n' : ' ');
        }
    }

    Pause();
    return EXIT_SUCCESS;
}


[此贴子已经被作者于2016-3-24 23:18编辑过]

2016-03-24 22:40
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
程序代码:
#include <cstdio>
#include <cstdlib>
#include <conio.h>

void Pause(void)
{
    printf_s("\nPress any key to continue...");
    _getch();
}

bool IsPrime(unsigned int n)
{
    if (n < 2)
    {
        return false;
    }

    if (n % 2 == 0)
    {
        return n == 2;
    }
    if (n % 3 == 0)
    {
        return n == 3;
    }
    if (n % 5 == 0)
    {
        return n == 5;
    }

    for (unsigned int i = 7; i * i <= n; i += 2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

bool Create_Prime_File(const char* filename)
{
    FILE* file;

    if (fopen_s(&file, filename, "wb") != 0)
    {
        return false;
    }

    for (unsigned int x = 0; x <= 0xffffff; ++x)
    {
        fputc(IsPrime(x), file);
    }
    fclose(file);

    return true;
}

const char* File_Name = "Prime_Number.DAT";
const size_t NUMBER_PER_ROW = 10;

int main(void)
{
    FILE* file;

    if (fopen_s(&file, File_Name, "rb") != 0)
    {
        if (!Create_Prime_File(File_Name))
        {
            return EXIT_FAILURE;
        }
        fopen_s(&file, File_Name, "rb");
    }

    /* 輸出10000-11000之間的素數 */
    size_t index = 0;
    for (unsigned int x = 10000; x <= 11000; ++x)
    {
        fseek(file, x, SEEK_SET);
        if (fgetc(file))
        {
            printf_s("%6u", x);
            putchar((++index % NUMBER_PER_ROW == 0) ? '\n' : ' ');
        }
    }

    fclose(file);

    Pause();
    return EXIT_SUCCESS;
}


[此贴子已经被作者于2016-3-25 00:08编辑过]


授人以渔,不授人以鱼。
2016-03-24 23:48
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
第一個例子,通過計算一個數是不是素數來判斷。
第二個例子,直接從預先生成的數據表中查找指定數據是不是素數,不需運算。

授人以渔,不授人以鱼。
2016-03-25 00:19
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
加點註釋
程序代码:
#include <cstdio>
#include <cstdlib>
#include <conio.h>

/*
功能: 暫停程序等待用戶鍵盤按鍵
*/
void Pause(void)
{
    printf_s("\nPress any key to continue...");
    _getch();
}

/*
功能: 判斷指定的整數是否素數
*/
bool IsPrime(unsigned int n)
{
    if (n < 2)
    {
        /* 0、1不是素數 */
        return false;
    }

    if (n % 2 == 0)
    {
        return n == 2;
    }
    if (n % 3 == 0)
    {
        return n == 3;
    }
    if (n % 5 == 0)
    {
        return n == 5;
    }

    for (unsigned int i = 7; i * i <= n; i += 2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

/*
功能: 建立素數分佈表
*/
bool Create_Prime_File(const char* filename)
{
    const unsigned int max = 0xffffff;        // 素數表値域,創建的文檔尺寸16M
    FILE* file;
    if (fopen_s(&file, filename, "wb") != 0)
    {
        return false;
    }
    for (unsigned int x = 0; x <= max; ++x)
    {
        fputc(IsPrime(x), file);
    }
    fclose(file);
    return true;
}

const char* File_Name = "Prime_Number.DAT";        // 素數表文件名
const size_t NUMBER_PER_ROW = 10;                // 輸出時每行顯示的數據數目

/*
功能: 程序入口
*/
int main(void)
{
    FILE* file;

    if (fopen_s(&file, File_Name, "rb") != 0)
    {
        if (!Create_Prime_File(File_Name))
        {
            return EXIT_FAILURE;
        }
        fopen_s(&file, File_Name, "rb");
    }

    /* 輸出素數 */
    unsigned int start = 1000000;
    unsigned int end = 1002000;
    size_t count = 0;
    fseek(file, start, SEEK_SET);
    for (unsigned int x = start; x <= end; ++x)
    {
        if (fgetc(file))
        {
            printf_s("%6u", x);
            putchar((++count % NUMBER_PER_ROW == 0) ? '\n' : ' ');
        }
    }

    fclose(file);

    Pause();
    return EXIT_SUCCESS;
}


最終的代碼,其實並不需要前面的IsPrime()和Create_Prime_File()函數。那個建立數據表的過程,是用於第一次創建的,該文件創建好後,就可以永久使用了。

[此贴子已经被作者于2016-3-25 10:22编辑过]


授人以渔,不授人以鱼。
2016-03-25 10:19
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:0 

一片落叶掉进了回忆的流年。
2016-03-25 10:26
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
有了這個數據表,現在返回最開始的用法:
程序代码:
#include <cstdio>
#include <cstdlib>
#include <conio.h>

const char* File_Name = "Prime_Number.DAT";        // 素數表文件名
const size_t NUMBER_PER_ROW = 10;                // 輸出時每行顯示的數據數目
FILE* hPrime;                                    // 素數表文件句柄

/*
功能: 暫停程序等待用戶鍵盤按鍵
*/
void Pause(void)
{
    printf_s("\nPress any key to continue...");
    _getch();
}

/*
功能: 判斷指定的整數是否素數
*/
bool IsPrime(unsigned int n)
{
    fseek(hPrime, n, SEEK_SET);
    return fgetc(hPrime) == 1;
}

/*
功能: 程序入口
*/
int main(void)
{
    if (fopen_s(&hPrime, File_Name, "rb") != 0)
    {
        return EXIT_FAILURE;
    }
    unsigned int start = 1000000;
    unsigned int end = 1002000;
    size_t count = 0;
    for (unsigned int x = start; x <= end; ++x)
    {
        if (IsPrime(x))
        {
            printf_s("%6u", x);
            putchar((++count % NUMBER_PER_ROW == 0) ? '\n' : ' ');
        }
    }
    fclose(hPrime);

    Pause();
    return EXIT_SUCCESS;
}

授人以渔,不授人以鱼。
2016-03-25 11:23
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
我認爲,在一般的應用中,擁有1670多萬範圍內的素數表已經足夠了。素數是死數,不用每次都計算,查表法一勞永逸,而且速度也最快。沒使用壓縮處理(用位表示可以把文檔尺寸壓縮至八分之一)的數據表文件尺寸是16M,這個尺寸在現在的計算機系統中,無需加載入內存也是很快的,第一次訪問文檔會稍慢,然而系統緩衝後已等於加載至內存,編程加載入內存,實際上是浪費資源,沒必要地增加複雜性。

授人以渔,不授人以鱼。
2016-03-25 18:37
林月儿
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:湖南
等 级:版主
威 望:138
帖 子:2277
专家分:10647
注 册:2015-3-19
收藏
得分:0 
愚以为你的注释加和不加差不多,能不能用简体中文啊?

剑栈风樯各苦辛,别时冰雪到时春
2016-03-25 21:55
我不信
Rank: 2
等 级:论坛游民
威 望:1
帖 子:33
专家分:24
注 册:2016-3-3
收藏
得分:0 
同上,但是可能是港澳台的也不一定
2016-03-25 21:59
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
就是不注释也看得懂

授人以渔,不授人以鱼。
2016-03-25 22:16
快速回复:關於素數的一些例子
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032314 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved