關於素數的一些例子 - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → 關於素數的一些例子

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 3271 人关注过本帖

标题：關於素數的一些例子

取消只看楼主加入收藏

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22
结帖率：100%

楼主

问题点数：0 回复次数：8

關於素數的一些例子

程序代码：

#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

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 2 楼

得分: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

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 3 楼

得分:0

第一個例子，通過計算一個數是不是素數來判斷。
第二個例子，直接從預先生成的數據表中查找指定數據是不是素數，不需運算。

授人以渔，不授人以鱼。

2016-03-25 00:19

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 4 楼

得分: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

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 5 楼

得分: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

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 6 楼

得分:0

我認爲，在一般的應用中，擁有1670多萬範圍內的素數表已經足夠了。素數是死數，不用每次都計算，查表法一勞永逸，而且速度也最快。沒使用壓縮處理（用位表示可以把文檔尺寸壓縮至八分之一）的數據表文件尺寸是16M，這個尺寸在現在的計算機系統中，無需加載入內存也是很快的，第一次訪問文檔會稍慢，然而系統緩衝後已等於加載至內存，編程加載入內存，實際上是浪費資源，沒必要地增加複雜性。

授人以渔，不授人以鱼。

2016-03-25 18:37

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 7 楼

得分:0

就是不注释也看得懂

授人以渔，不授人以鱼。

2016-03-25 22:16

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 8 楼

得分:0

看不懂的不看就可以了

授人以渔，不授人以鱼。

2016-03-26 17:29

TonyDeng

等　级：贵宾
威　望：304
帖　子：25859
专家分：48889
注　册：2011-6-22

第 9 楼

得分:0

現在改一下，把素數函數庫封裝到模塊中。

main.cpp:

程序代码：

#include <cstdio>
#include <cstdlib>
#include <conio.h>
#include "Prime.h"

void Pause(void);

const size_t NUMBER_PER_ROW = 10;

int main(void)
{
    OpenPrimeFile();

    unsigned int start = 1000000U;
    unsigned int end = 1002000U;
    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' : ' ');
        }
    }

    ClosePrimeFile();

    Pause();
    return EXIT_SUCCESS;
}

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

Prime.h:

程序代码：

#pragma once

bool OpenPrimeFile(void);
void ClosePrimeFile(void);
bool IsPrime(unsigned int n);

Prime.cpp:

程序代码：

#include <cstdio>
#include <cstdlib>
#include "Prime.h"

const char* File_Name = "Prime_Number.DAT";        // 素數表文件名
FILE* hPrime = NULL;                            // 素數表文件句柄

bool OpenPrimeFile(void)
{
    return (fopen_s(&hPrime, File_Name, "rb") == 0);
}

void ClosePrimeFile(void)
{
    if (hPrime)
    {
        fclose(hPrime);
    }
}

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

授人以渔，不授人以鱼。

2016-03-26 19:31

快速回复：關於素數的一些例子