自承式光缆 numpy SQLMAP iphone cordova silverlight ionic3 chartjs NEC Font Awesome vue框架 vue原理 河南普通话考试 pr序列设置哪个好 java遍历json数组 edate函数的使用方法 oracle重命名表名 python练习题 mysql教程 python入门教程 python程序实例 python学习方法 java实现接口 搭建java开发环境 java集合类 java的集合 linux目录 bcdautofix sp5 microkms 主板芯片组天梯图 ps插入表格 pyh 易语言多线程 编程语言实现模式 游戏python界面编程 猫眼电影票 fastcgi 暴力猴 英特尔显卡驱动官方
当前位置: 首页 > 学习教程  > 编程语言

C语言学习笔记:素数筛法

2020/10/8 18:38:52 文章标签:

“筛法”是一种求素数的方法。是公元前300年左右由古希腊著名数学家埃拉托色尼提出的,埃拉托色尼把自然数1、2、3、4、……写在一块涂了一层白蜡的板上,将去掉数的地方用工具刺成小孔,很像一个筛子。因为用它把所有的合数都筛掉,留…

“筛法”是一种求素数的方法。是公元前300年左右由古希腊著名数学家埃拉托色尼提出的,埃拉托色尼把自然数1、2、3、4、……写在一块涂了一层白蜡的板上,将去掉数的地方用工具刺成小孔,很像一个筛子。因为用它把所有的合数都筛掉,留下的都是质数,所以,人们把这种求质数的方法叫做“筛法”。
用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。

那“筛法”如何在C语言实现呢?

现在给你一个正整数N,要你快速的找出在2.....N这些数里面所有的素数。
输入 给出一个正整数数N(N<=2000000)
输出 将2~N范围内所有的素数输出。两个数之间用空格隔开

下面我们使用筛法来求解这道题:

埃拉托色尼把自然数1、2、3、4、……写在一块涂了一层白蜡的板上,而我们可以创建一个数组来模拟这一行为:
声明一个长度为N+1的布尔数组A[N+1]。用这个数组来表示对应下标的数字是不是素数,而数组内每个对应的值则代表小孔。
起初,将数组所有成员标记为1,然后按照某种方法将其中的非素数都标记为0,这样下来咱们的“板子”就创建好了

#include <stdio.h>
#include <math.h>//素数判断函数使用
#include <stdlib.h>
int *a = NULL;
int n = 0;
int main()
{
    scanf("%d", &n);                          //输入n
    a = (int *)malloc(sizeof(int) * (n + 1)); //创建数组a[n+1]
    for (int i = 0; i < n + 1; i++)           //初始化,所有元素等于1
    {
        a[i] = 1;
    }
    /*此处放素数判断函数*/
    free(a);
    return 0;
}

完成后的数组有这样的特征:所有素数为下标的成员内存的数字都是1,所有非素数为下标的成员内存的数字都是0。
接下来就是“点小孔”了:
判断一i是否为素数,最简单的方法是用循环判断每个小于i的整数能否整除i:

int judge()
{
    for (int i = 1; i <= n; i++) //循环小于等于n的所有数i
    {
        for (int j = 2; j < i; i++) //判断i是否为素数
        {
            if (i % j == 0)
            {
                a[i] = 0;
                break;
            }
        }
    }
    return 0;
}

若使用筛法判断,当我们判断出是素数后,将此素数的倍数都变为非素数:

int prime_judge()
{
    a[0] = 0;                    //0、1不是素数
    a[1] = 0;
    for (int i = 1; i <= n; i++) //循环小于等于n的所有数
    {
        if (a[i]) //若i为素数
        {
            for (int j = 2 * i; j <= n; j += i) //所有i的倍数都不是素数
                a[j] = 0;
        }
    }
    return 0;
}

当然这个方法已经有很大的改进了,但是仍然存在会有重复筛掉某一合数,增加无用计算的现象,例如,删3的倍数时15标记为0,删15的倍数时,同样再一次将15标记为0。这还不够精简,因此有人将这个方法进行了改进:

int prime_judge()
{
    a[0] = 0; //0、1不是素数
    a[1] = 0;
    for (int i = 4; i <= n; i += 2) //除2外,偶数都不为素数
    {
        a[i] = 0;
    }
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (a[i]) //如果i是素数
        {
            for (int j = i * i; j <= n; j += 2 * i) //所有i的倍数都不是素数
                a[j] = 0;
        }
    }

    return 0;
}

最后是总体代码:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int *a = NULL;
int n = 0;
int main()
{
    scanf("%d", &n);                          //输入n
    a = (int *)malloc(sizeof(int) * (n + 1)); //创建数组a[n+1]
    for (int i = 0; i < n + 1; i++)           //初始化,所有元素等于1
    {
        a[i] = 1;
    }
    prime_judge();
    prime_view();
    free(a);
    return 0;
}

int prime_judge()
{
    a[0] = 0; //0、1不是素数
    a[1] = 0;
    for (int i = 4; i <= n; i += 2) //除2外,偶数都不为素数
    {
        a[i] = 0;
    }
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (a[i]) //如果i是素数
        {
            for (int j = i * i; j <= n; j += 2 * i) //所有i的倍数都不是素数
                a[j] = 0;
        }
    }

    return 0;
}
int prime_view()
{
    for (int i = 0; i < n + 1; i++)
    {
        if (a[i])
        {
            printf("%d ", i);
        }
    }

    return 0;
}


本文链接: http://www.dtmao.cc/news_show_250078.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?