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

楼主

问题点数：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编辑过]

第 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编辑过]

授人以渔，不授人以鱼。

第 3 楼

得分:0

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

授人以渔，不授人以鱼。

第 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编辑过]

授人以渔，不授人以鱼。

第 5 楼

得分:0

一片落叶掉进了回忆的流年。

第 6 楼

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

授人以渔，不授人以鱼。

第 7 楼

得分:0

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

授人以渔，不授人以鱼。

第 8 楼

得分:0

愚以为你的注释加和不加差不多，能不能用简体中文啊？

剑栈风樯各苦辛，别时冰雪到时春

第 9 楼

得分:0

同上，但是可能是港澳台的也不一定

第 10 楼

得分:0

就是不注释也看得懂

授人以渔，不授人以鱼。