LightOJ1259 Goldbach`s Conjecture —— 素数表
题目链接:https://vjudge.net/problem/LightOJ-1259
Time Limit: 2 second(s) | Memory Limit: 32 MB |
Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:
Every even integer, greater than 2, can be expressed as the sum of two primes [1].
Now your task is to check whether this conjecture holds for integers up to 107.
Input
Input starts with an integer T (≤ 300), denoting the number of test cases.
Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).
Output
For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where
1) Both a and b are prime
2) a + b = n
3) a ≤ b
Sample Input |
Output for Sample Input |
2 6 4 |
Case 1: 1 Case 2: 1 |
Note
- An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, ...
题意:
哥德巴赫猜想:任何一个大于2的偶数,都可以是两个素数的和。给出一个偶数,判断有多少对素数的和是这个数。
题解:
由于n<=1e7,所以我们可以先筛选出1e7范围内的素数,然后再枚举每一个素数进行判断。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e7+; bool notprime[MAXN];
int prime[];
void getPrime()
{
memset(notprime, false, sizeof(notprime));
notprime[] = notprime[] = true;
prime[] = ;
for (int i = ; i<=MAXN; i++)
{
if (!notprime[i])prime[++prime[]] = i;
for (int j = ; j<=prime[ ]&& prime[j]<=MAXN/i; j++)
{
notprime[prime[j]*i] = true;
if (i%prime[j] == ) break;
}
}
} int main()
{
getPrime();
int T, n, kase = ;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans = ;
for(int i = ; prime[i]<=n/; i++)
if(!notprime[n-prime[i]])
ans++;
printf("Case %d: %d\n", ++kase,ans);
}
return ;
}
最新文章
- CoordinatorLayout+TabLayout+ViewPager
- codeforce B Island Puzzle
- Deep Learning 6_深度学习UFLDL教程:Softmax Regression_Exercise(斯坦福大学深度学习教程)
- UML3
- Highcharts 连续的堆积面积图
- JavaScript高级程序设计之寄生组合式继承
- [转] POJ数学问题
- Codeforces Round #327 (Div. 2) E. Three States BFS
- Python机器学习包
- [译]Python作为一种编程语言有多强大?
- 21 FragmentTabHost +Fragment代码案例
- Java实现堆的封装,进行插入,调整,删除堆顶以完成堆排序实例
- 【XSY2962】作业 数学
- Python脚本备份
- [深度学习] 权重初始化--Weight Initialization
- generatorConfiguration详解
- Hdu1241 Oil Deposits (DFS)
- C#检测是否联网
- vue2.0中使用less
- [转载]Tomcat部署与配置
热门文章
- Nginx+keepalived双机热备(主从模式)
- .net 哈希
- 转载cookie理解
- 深入Android渲染机制
- Android View 布局流程(Layout)完全解析
- win7 32位配置apache+wsgi+django环境
- Java中的BigInteger在ACM中的应用
- C# 将long类型写入二进制文件用bw.Write(num);将其读出用long num= br.ReadInt64();
- 求助大神!怎样除去XML节点反复的值的数据
- JMeter中使用Put请求方式请求接口