注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xum1246.素数筛选  

2011-11-16 22:21:55|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1246.素数筛选
Time Limit: 2000 MS         Memory Limit: 65536 K
Total Submissions: 534 (72 users)         Accepted: 63 (40 users)
[ My Solution ]

Description

请求出区间[A,B]之间的素数的个数。

Input
输入有多组数据。
第一行为正整数T(T<10),表示输入的数据组数。
第二行到第T+1行,每行2个数字A,B(0<A<=B<2^31,且B-A<2^20)表示区间的范围。

Output

输出T行数字,每行只有一个数字,表示对应的素数的个数。

Sample Input

2
100 200
2 1000000

Sample Output

21
78498

Source
 
区间求素数的个数,用筛选法来做。
#include <stdio.h>  
#include <string.h>  
#include <math.h>  
#define maxn 1050000
int L,U;
int p[maxn], sz;
bool flag[maxn];
inline int sieve(int L,int U)
{
  int d = U - L + 1, i, limit=(int)sqrt((double)U);
  for(i = 0; i < d; i++) flag[i] = true;
  for(i = L & 0x1; i < d; i += 2) flag[i] = false;
  for(i = 3; i <= limit; i += 2)
  {
    if(i > L && flag[i-L] == false) continue;
    int j = L / i * i;
    if(j < L) j += i;
    if(j == i)j += i;
    j = j - L;
    for(; j < d; j += i) flag[j]=false;
  }
  if(L <= 1) flag[1-L] = false;
  if(L <= 2) flag[2-L] = true;
  sz=0;
  for(i=0;i<d;i++)
   if(flag[i]==true)
    p[sz++]=i+L;
return sz;
}
 
int main()  
{  
     int t, a, b;   
        scanf("%d", &t);  
        while(t--)  
        {  
         scanf("%d %d", &a, &b);  
          printf("%d\n", sieve(a, b));  
        }  
return 0;  

  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017