精华内容
下载资源
问答
  • c语言筛选法

    2013-06-25 08:53:53
    一个接触即会的c语言筛选方法 方法新颖独特
  • C语言筛选法求素数

    2020-04-01 14:13:50
    i+=2) { if(arr[i-1]==0) //在第一轮筛选后的元素中继续筛选 { //j表示3-100的元素; //目的是将3的倍数置为1,依次4的倍数... //注意这里的初值为i*i,增量为2*i //之所以可以这么做,是因为3的倍数,除了本身,即乘1...

    素数的定义:素数也即质数;在大于1的自然数中,除了1和他本身以外没有其他的因数,我们称之为素数。

    问题:求出1-100之内的素数。

    方法1,利用定义直接遍历
    #include<stdio.h>
    #include<math.h>
    //思路:优化了j的范围而非(2-i)因为如果一个数不能被从2到其开方的数整除,其即为素数
    //时间复杂度:nlog2n
    void main()
    {
        int i,j,k;
        for(i=1;i<=100;i++)
            {
               int k = sqrt(i);
                for(j=2;j<=k;j++)
                {
                    if(i%j==0)
                        break;
                }
                if(j>k)//全部循环完后,j>k,此时就是素数;因为只要中途退出一次就有j<=k
                printf("%4d",i);
            }
    }
    
    方法二,利用数组筛选

    1.原理:1-100存放于数组中,首先1不是素数,筛掉;从2开始,能被整除的,即2的倍数,都不是,筛掉;然后是3,3的倍数筛掉;然后是5,7,11…
    2. 思路:设置一个容量100的数组存放1-100;初始值为0;如果不为素数,置为1表示筛掉;最后遍历数组输出值为0的元素即可。
    3. 目的:本例使用数组筛选的目的是使时间复杂度将到最低,所以还有其他利用数组筛选的方法。

    #include<stdio.h>
    #include<math.h>
    #define N 100
    int main()
    {
        int arr[N]={0}; //使用(索引+1)表示1-100个数
        arr[0]=1;        //1不是素数,首先筛选出来
        int i;          //i表示索引,也即元素
        for(i=2;i<=N;i++)    //第一轮:筛选掉2的倍数,
        {
           if(i%2==0)
           {
               arr[i-1] = 1;
           }
        }
        arr[1] = 0; //2是素数,因为2也是2的倍数会在第一轮中被误筛
        for(i=3;i<sqrt(N);i+=2) 
        {
            if(arr[i-1]==0) //在第一轮筛选后的元素中继续筛选
            {
                //j表示3-100的元素;
                //目的是将3的倍数置为1,依次4的倍数...
                //注意这里的初值为i*i,增量为2*i
                //之所以可以这么做,是因为3的倍数,除了本身,即乘1之外,乘2,为2的倍数(第一轮筛掉了),然后就是3乘3,所以初值为i*i;
                //同理,3*4,pass;3*5=3*3+3*2;所以增量为2*i;依次...
                for(int j=i*i;j<=N;j+=2*i)
                {
                    arr[j-1]=1;
                }
            }
        }
        //打印数组
        for(i=0;i<N;i++)
        {
            if(arr[i]==0)
            {
                printf("%2d ",i+1);
            }
        }
        return 0;
    }
    

    参考来源:https://blog.csdn.net/weixin_38679924/article/details/88536802
    有其他更简单的方法,欢迎指出。

    展开全文
  • c语言筛选法求素数

    千次阅读 2017-01-23 10:19:09
    使用了动态内存分配,求给定区间里面所有的素数, #include #include int main() ...参考了网上的筛选法,自己添加的动态内存。 因为不知道具体操作时候的内存有多大,所以使用了动态内存

    使用了动态内存分配,求给定区间里面所有的素数,

    #include<stdlib.h>
    #include<stdio.h>
    int main()
    {
    int n,i,a,b;int *p;
    scanf("%d",&n);
    p=(int *)calloc(n,sizeof(int));
    for(i=2;i<=n;i++)
    {
    if(*(p+i)==0)
    for(a=2;a*i<=n;a++)
    *(p+(a*i))=1;
    }
    for(i=2;i<=n;i++){
    if(*(p+i)==0)
    printf("%dn",i);
    }

    return 0;
    }

    参考了网上的筛选法,自己添加的动态内存。

    因为不知道具体操作时候的内存有多大,所以使用了动态内存

    展开全文
  • 筛选求质数明除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个着名的 Eratosthenes求质数方法。行文不易,新手上路...

    eed3ca519676cfe3da8c82de8864b645.png

    筛选求质数

    明除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个着名的 Eratosthenes求质数方法。

    380ad9d0354a009d345eb04043211376.png
    行文不易,新手上路,多多关注,这真的对我很重要,私信更有惊喜

    首先知道这个问题可以使用回圈来求解,将一个指定的数除以所有小于它的数,若可以整除就不是质数,然而如何减少回圈的检查次数?如何求出小于N的所有质数?首先假设要检查的数是N好了,则事实上只要检查至N的开根号就可以了,道理很简单,假设A*B = N,如果A大于N的开根号,则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题,所以可以使用 i*i <= N进行检查,且执行更快。
    再来假设有一个筛子存放1~N,例如:23 456789101112131415161718192021 ....N
    先将2的倍数筛去:23 579111315171921....N
    再将3的倍数筛去:23 5711131719....N
    再来将5的倍数筛去,再来将7的质数筛去,再来将11的倍数筛去........,如此进行到最后留下的数就都是质数,这就是Eratosthenes筛选方法(Eratosthenes Sieve Method)。检查的次数还可以再减少,事实上,只要检查6n + 1与6n + 5就可以了,也就是直接跳过2与3的倍
    数,使得程式中的if的检查动作可以减少源码实现

    33291c77343a41edb4b2871594ffc89e.png
    行文不易,新手上路,多多关注,这真的对我很重要,私信更有惊喜
    展开全文
  • 23 579111315171921....N 再将3的倍数筛去: 23 5711131719....N 再来将5的倍数筛去,再来将7的质数筛去,再来将11的倍数筛去........,如此进行到最后留下的数就都是质数,这就是Eratosthenes筛选方法...
    156f5737316212b2ea1d311db974295f.png

    小编是一个有着6年工作经验的工程师,关于C++编程,自己有做材料的整合,一个完整的C++编程学习路线,学习资料和工具,能够进我的群10048,-83029收取,免费送给大家,希望你也能凭着自己的努力,成为下一个优秀的程序员

    43e3dae358d4617e3d8ea7597191699a.png

    明除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个着名的 Eratosthenes求质数方法。

    6b51fb8c9df093afdb41cc746d2ea929.png

    首先知道这个问题可以使用回圈来求解,将一个指定的数除以所有小于它的数,若可以整除就不是质数,然而如何减少回圈的检查次数?

    如何求出小于N的所有质数?

    首先假设要检查的数是N好了,则事实上只要检查至N的开根号就可以了,道理很简单。

    假设A*B = N,如果A大于N的开根号,则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。

    不过在程式中使用开根号会精确度的问题,所以可以使用 i*i <= N进行检查,且执行更快。

    再来假设有一个筛子存放1~N,例如:

    23 456789101112131415161718192021 ....N

    先将2的倍数筛去:

    23 579111315171921....N

    再将3的倍数筛去:

    23 5711131719....N

    再来将5的倍数筛去,再来将7的质数筛去,再来将11的倍数筛去........,如此进行到最后留下的数就都是质数,这就是Eratosthenes筛选方法(Eratosthenes Sieve Method)。

    检查的次数还可以再减少,事实上,只要检查6n + 1与6n + 5就可以了,也就是直接跳过2与3的倍数,使得程式中的if的检查动作可以减少

    3e161ab590dceea70fc3343b849bdefb.png

    这个算法,你懂了吗?

    展开全文
  • 素数数量 C语言用这种解法,你会发现是所有人种最快的; 代码: #include int main() { int i,j,n,a[1000001]={0}; for(i=2;i;i++) { for(j=i*i;j;j+=i) a[j]=1; } for(i=2;i;i++) { if(!a[i]) a[i]=a[i-1]+1; /*这两...
  • C语言筛选法

    千次阅读 2019-10-16 22:45:07
    1.用筛选法求100之内的素数; 筛选法:1不是素数,划去; 2是素数,留下,将2的倍数划去; 3没被划去,将3的倍数划去; 以此类推,将i的倍数划去; 留下的就是素数; 下面是实现的代码:两种均可,只有一点细微区别...
  • c语言筛选法

    2019-10-24 21:29:52
    例:用筛选法求100以内的素数 首先解释一下筛选法的步骤: <1> 先将1挖掉(因为1不是素数)。 <2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。 <3> 用3去除它后面的各数,把3的...
  • C语言】 利用筛选法求100以内的素数

    万次阅读 多人点赞 2018-10-27 09:41:29
    //C语言 筛选法求100以内的素数 //原理很简单,就是当i是质(素)数的时候,i的所有的倍数必然是合数。如果i已经被判断不是质数了,那么再找到i后面的质数来把这个质 //数的倍数筛掉。 //我们将从2开始 用2除后面的数...
  • C语言筛选法求素数

    千次阅读 2018-04-23 21:11:36
    筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3...
  • 用简单素数筛选法求N以内的素数。 输入: N 输出: 2~N的素数 代码如下: #include<stdio.h> int main() { int N; scanf("%d",&N); for(int i=2;i<=N;i++) { int k=0; for(int j=2;j<...
  • # 用筛选法求m和n之间的所有素数 求大神帮忙看看怎么写这个代码 实在写不出来 ``` #include "stdio.h" main() { int a[1000]={0},i,j,m,n; scanf("%d%d",&m,&n); @@2 对数组作筛选法处理 @@2 ...
  • 素数筛选prime seive算法C语言素数筛选prime seive算法完整源码(定义,实现,main函数测试) C语言素数筛选prime seive算法完整源码(定义,实现,main函数测试) #include <assert.h> /// for assert #...
  • D_Prime [ Submit Code ] [ Top 20 Runs ] [ Runs Status ] Acceteped : 777 Submit : 2849 Time Limit : 2000 MS Memory Limit : 65536 KB Description ...整数n=p*q,p和q为质数,且p≠q,我们称n为D-...
  • } } printf("用筛选法求出的100以内的素数:\n"); for(i=1;i;i++) { if(a[i]!=0) { printf("%4d",a[i]); k++; } if(k%10==0) printf("\n"); } printf("\n"); return 0; } 具体解析可以参考这篇...
  • 生成素数 筛选法 C语言

    千次阅读 2011-04-09 00:27:00
    生成素数 C语言 筛选法   #include #include #define N 100000 void main() { int a[N]; //筛子数组 int i,num; int minp,doub; //minp筛选种子,doub倍数 int n=0; //素数个数,用于...
  • 筛选法求解素数问题C语言实现

    千次阅读 2019-03-13 17:06:55
    3.在第二轮非素数筛选时,因为是从所有奇数中按从小到大的顺序筛选素数的,由归纳不难得知: 若i = 3为素数,则因为在第一轮筛序中已经将2的倍数的数排除了,故可直接从j = 3 * 3开始进行非素数的筛选; 若i = 5...
  • 问题:用筛选法求100以内的素数 二.程序如下: #include<stdio.h> int main(void) { int a[101],i,j,n; //定义数组a:包含101个元素 for(i=1;i<101;i++) //a[0]不用,只用a[1]-a[100]; a[i]=i; ...
  • 筛选法求100之内的素数 首先我们来看一下什么是素数: 素数又称质数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除; 介绍一下筛选法筛选法所谓"筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”...
  • Eratosthenes筛选法是一种计算质数的有效方法。 这个算法的第一步就是写下所有从2至某个上限之间的所有整数。 在算法的剩余部分,遍历整个列表并剔除所有不是质数的整数。 后面的步骤是这样的。 找到列表中的第...
  • 什么是筛选法筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把...
  • 筛选法求100之内的素数 #include <stdio.h> #include <math.h> void main(){ int i,j,n,a[101]; for(int i=1;i<=100;i++){ a[i]=i; } a[1]=0; for(i=2;i<sqrt(100);i++){ for(j=i+1;j<...
  • 筛选法求100之内的素数(C语言 数组)

    万次阅读 多人点赞 2018-05-21 11:28:28
    1.解释下什么是筛选法? 筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 182
精华内容 72
关键字:

c语言筛选法

c语言 订阅