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

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

一道关于素数的题目  

2009-03-24 14:45:19|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

Fermat's Christmas Theorem

Acceteped : 24   Submit : 373
Time Limit : 1000 MS   Memory Limit : 65536 KB
 

Description

In a letter dated December 25, 1640; the great mathematician Pierre de Fermat wrote to Marin Mersenne that he just proved that an odd prime p is expressible as p = a2 + b2 if and only if p is expressible as p = 4c + 1. As usual, Fermat didn’t include the proof, and as far as we know, never wrote it down. It wasn’t until 100 years later that no one other than Euler proved this theorem. To illustrate, each of the following primes can be expressed as the sum of two squares:

5 = 22 + 12 13 = 32 + 22 17 = 42 + 12 41 = 52 + 42

Whereas the primes 11, 19, 23, and 31 cannot be expressed as a sum of two squares. Write a program to count the number of primes that can be expressed as sum of squares within a given interval.

Input

Your program will be tested on one or more test cases. Each test case is specified on a separate input line that specifies two integers L, U where LU < 1,000,000.

The last line of the input file includes a dummy test case with both L = U = ?1.

Output

For each test case, write the result using the following format:

L U x y

where L and U are as specified in the input. x is the total number of primes within the interval [L, U] (inclusive), and y is the total number of primes (also within [L, U]) that can be expressed as a sum of squares.

 

Sample Input

10 20
11 19
100 1000
-1 -1
 

Sample Output

10 20 4 2
11 19 4 2
100 1000 143 69
 

Source

Arab and North Africa 2007
 
题目大意:寻找给定区间范围内素数的个数,以及在这些素数中可以表示为a2 + b2的数的个数。
主要思想:如果采用朴素判断法对每个给定的区间分别处理,一定会超时。在这里可以通过预处理的办法,用筛选法先找出1~1,000,000内所有素数,然后只需要在已经得到的约8,000个素数范围内进行处理就可以了。
注意问题:
1.给出的测试数据范围可以从-999,999~999,999,在这个范围下如果遍历未处理的数组n遍,一定会超时。
2.注意2的特殊性,2并不满足p = 4c + 1的关系式,但是可以拆成12 +12,所以2是这道题里的一个特殊情况。
代码如下:
#include
#include
#define MAX 1000000
using namespace std;
bool prime[MAX];
int p[MAX];
int main(){
    int l,u;
    int i,j,nPSum,nSSum;
    //下面用筛选法找到1~1,000,000内的素数
    prime[0]=false;prime[1]=false;
    for(i=2;i    for(i=2;i<(int)sqrt((double)MAX);i++){
        if(prime[i])
            for(j=i;j*i    }
    j=0;
    for(i=2;i
        if(prime[i])p[++j]=i;//将所有素数转到一个数组中,降低下面的遍历的时间
    }
    p[0]=j;
    scanf("%d%d",&l,&u);
    while(l!=-1||u!=-1){
        nPSum=nSSum=0;
        for(i=1;i<=p[0];i++){
            if(p[i]>=l&&p[i]<=u){//遍历素数表,如果当前数据在l~u的范围内进行相应的处理
                nPSum++;
                if(p[i]==2)nSSum++;//这里要对2进行特殊处理
                else if((p[i]-1)%4==0)nSSum++;
            }
            if(p[i]>u)break;//如果当前的素数超出了上界就结束
        }
        printf("%d %d %d %d ",l,u,nPSum,nSSum);
        scanf("%d%d",&l,&u);
    }
    return 0;
}
后记:对特殊情况的处理有时候就是整道题目的关键,一定要仔细分析。当然,这种解法的时间复杂度还不是很理想,就留待以后进一步改进吧。
  评论这张
 
阅读(333)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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