Codeforces 113C
C. Double Happinesstime limit per test5 seconds
memory limit per test128 megabytes
inputstandard input
outputstandard output
On the math lesson a teacher asked each pupil to come up with his own lucky numbers. As a fan of number theory Peter chose prime numbers. Bob was more original. He said that number t is his lucky number, if it can be represented as:
t = a2 + b2, where a, b are arbitrary positive integers.
Now, the boys decided to find out how many days of the interval [l, r] (l ≤ r) are suitable for pair programming. They decided that the day i (l ≤ i ≤ r) is suitable for pair programming if and only if the number i is lucky for Peter and lucky for Bob at the same time. Help the boys to find the number of such days.
InputThe first line of the input contains integer numbers l, r (1 ≤ l, r ≤ 3·108).
OutputIn the only line print the number of days on the segment [l, r], which are lucky for Peter and Bob at the same time.
Sample test(s)input3 5output1input6 66output7
/*************************************************************************
> File Name: 113C.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年07月20日 星期日 13时34分53秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <bitset>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = 1e8+1e8+1e8;
bitset<maxn> p; int
main(void) {
int L, R;
scanf("%d %d\n", &L, &R);
p.set();
for (int i = ; i*i <= R; i+=) if (p[i]) for (int j = i*i; j <= R; j+=*i) p[j] = false;
int ans = ;
for (int i = ; i <= R; i+=) if (p[i] && i >= L) ans++;
ans += (L <= && R >= ) ? : ;
printf("%d\n", ans); return ;
}
最新文章
- ASP.NET MVC5+EF6+EasyUI 后台管理系统(45)-工作流设计-设计步骤
- Leetcode Search for a Range
- sql之truncate 、delete与drop区别
- Java 线程 — synchronized、volatile、锁
- SSH客户端(如PuTTY)ssh远程登录Linux非常慢的解决方法
- hdu 1203 I NEED A OFFER (0-1背包)
- mysql实例 保存查询结果到变量
- phpcms V9 首页模板文件解析(转)
- 原生js实现轮播
- mvc 母版页、用户自定义控件
- WebApi接收复杂类型参数
- 【netty这点事儿】ByteBuf 的使用模式
- Yii2.0源码阅读-behavior的实现原理
- loadrunner-参数化
- CSS中清除浮动的作用以及如何清除浮动
- Hadoop记录-Ganglia监控HDFS和HBase指标说明
- 个人博客作业-Week1
- BZOJ4785 ZJOI2017树状数组(概率+二维线段树)
- android 同时打开两个sqlite database db
- 网易云信&;七鱼市场总监姜菡钰:实战解读增长黑客在B端业务的运用