Chinaunix首页 | 论坛 | 博客
  • 博客访问: 586614
  • 博文数量: 197
  • 博客积分: 7001
  • 博客等级: 大校
  • 技术积分: 2155
  • 用 户 组: 普通用户
  • 注册时间: 2005-02-24 00:29
文章分类

全部博文(197)

文章存档

2022年(1)

2019年(2)

2015年(1)

2012年(100)

2011年(69)

2010年(14)

2007年(3)

2005年(7)

分类: C/C++

2012-05-26 08:42:01


Anti-Goldbach's Conjecture

哥德巴赫猜想:

任一大于2的偶数,都可表示成两个素数之和。

是世界上最著名的未解问题之一,但是下面的反哥德巴赫猜想:

任一大于11的奇数,都可表示成两个合数之和。

确很容易证明。

定义反哥德巴赫分拆数g(n)表示将大于11的奇数n分解为两个合数之和的方案数。再定义sg(n)=sum({g(i) | i ≤ n}),即所有不大于n的奇数的反哥德巴赫分拆数之和。你的任务就是快速的计算给定n所对应的sg(n)

Input

有大约100组测试数据。每组测试数据占一行,包含唯一的一个正整数13 ≤ n ≤ 1000000。输入以EOF结束。

Output

对于输入n,输出对应的sg(n)

Sample Input

13

14

15

Sample Output

1

1

2

 

由题目意思可得:

 

sg[n]=sg[n-2]+g[n]; 1)非常明显可以得到

 g[n]=g[n-2]+;  2//composite[n]表示n是否为素数

 解释一下等式(2)。因为g[n-2]是奇数,对于它的任何一个有效分解都是奇数X和偶数YY>=4),XY+2Y+2必然是合数)必然是g[n]的一个有效分解。而(n-4,2)必然不是g[n-2]的分解,但是数对(n-4,4)可能是g[n]的有效分解,所以引入composite[]数组。

很显然,我们首先可以算出数组composite,然后利用式(2(1)计算出g[]sg[]


#include
#include
#include
#include
using namespace std;

#ifdef  _MSC_VER
typedef __int64 LL;
#else
typedef long long LL;
#endif


const int MAXN=1<<20;
int composite[MAXN];//是否合数数组
LL sg[MAXN];

int main()
{
    int i,n;
   
   
     for(i=2;i        if(!composite[i]){
            for(int j=i+i;j                composite[j]=1;
        }
    }
    sg[11]=0;
    int g=0; //g代表g(n)
    for(i=13;i        g+=composite[i-4];
        sg[i]=sg[i-2]+g;
    }

    while(~scanf("%d",&n)){
        printf("%lld\n", n%2?sg[n]:sg[n-1]);
    }
    return 0;
}

阅读(1241) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~