| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1856 人关注过本帖
标题:求素数的另类方法
只看楼主 加入收藏
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1743
专家分:3216
注 册:2015-12-2
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:8 
求素数的另类方法
基本思路是先设某个范围内所有数全为素数。
然后从最小素数的倍数开始去除合数,然后从第二小的素数倍数去除合数,直
至所有合数去除完成。
这种求素数方法效率相当高,我试了一下求100以内的素数只须跑4次循环,
求1000以内的素数只须跑11次。
不多说贴代码:
#include <stdio.h>
#define MAXNUM 1000
main ()
{
    int prime[MAXNUM];            //记录数据类型,1为素数,0为合数
    int i,j,c=0,count=0;
    for( i=2;i<MAXNUM;i++)
    {
        prime[i]=1;                //初始化数组
    }
    for(i=2;i*i<MAXNUM;i++)
    {
        if(prime[i]==1)         
        {
            for(j=i*2;j<MAXNUM;j++)
            {
                if(!prime[j])continue;
                if(j%i==0)prime[j]=0;     //是合数置0
            }
        count++;   
        }
     }
     for(i=2;i<MAXNUM;i++)
     {
         if(prime[i]==1)
         {
             c++;
             printf("%2d ",i);
             if(c%10==0)
             printf("\n");
         }
         
         
     }
     printf("\n走了%d次循环",count);
}
搜索更多相关主题的帖子: 素数 类方法 count for i++ 
2018-09-01 19:13
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:4 
学习了
2018-09-01 19:16
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:4 
这个方法是……
只是知道目前为止欧拉筛最快~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-09-01 19:27
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1743
专家分:3216
注 册:2015-12-2
收藏
得分:0 
回复 3楼 九转星河
比欧拉筛如何?
2018-09-01 19:32
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 4楼 ehszt
什么?
加了行代码,瞬间从11次循环变成了10691次循环,欧拉筛才跑了1000次,服了!

其实这个实质就是一个普通筛法,当遍历合数不只有两个因子时重复时会重复遍历~
~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-09-01 21:10
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1743
专家分:3216
注 册:2015-12-2
收藏
得分:0 
回复 5楼 九转星河
加了什么代码?
你确认会重复遍历?
举个栗子!
2018-09-01 21:21
zhangchm2018
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:32
专家分:129
注 册:2018-8-18
收藏
得分:4 
回复 3楼 九转星河
跟欧拉筛的区别:
只是标记素数的布尔值不同
2018-09-01 22:26
幻紫灵心
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:山咔咔里面
等 级:贵宾
威 望:53
帖 子:395
专家分:2640
注 册:2018-3-30
收藏
得分:4 
程序代码:
for(i=2;i*i<MAXNUM;i++)
    {
        if(prime[i]==1)         
        {
            for(j=i*2;j<MAXNUM;j++)
            {
                count++;    //计数不应该放在这里吗???一万多次。。。。
                if(!prime[j])continue;
                if(j%i==0)prime[j]=0;     //是合数置0 
            }
        }
     } 

saber,别哭.
2018-09-02 23:21
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 6楼 ehszt
不另类,常规操作~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-09-03 16:29
快速回复:求素数的另类方法
数据加载中...
 
   



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

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