/*
* UVA_10533.cpp
*
* Created on: 2013年10月7日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000001;
bool u[maxn];
int u2[maxn];
void prepare() {
int i, j;
memset(u, true, sizeof(u));
for (i = 2; i <= maxn; ++i) {
if (u[i]) {
for (j = 2; j * i <= maxn; ++j) {
u[j * i] = false;
}
}
}
}
bool ok(int x) {
int k = 0;
while (x) {
k += x % 10;
x /= 10;
}
return u[k];
}
int main() {
prepare();
int t;
scanf("%d", &t);
int i, j;
for (i = 2; i <= maxn; ++i) {
if (u[i] && ok(i)) {
u2[i] = 1;
}
}
for (i = 2; i <= maxn; ++i) {
u2[i] += u2[i - 1];
}
while (t--) {
scanf("%d%d", &i, &j);
printf("%d\n", u2[j] - u2[i - 1]);
}
return 0;
}
分享到:
相关推荐
埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。
本ppt用于,数论基础授课,整体内容较为基础,ppt内容包括:素数筛、组合排列、最大公因数最小公倍数(gcd、lcm)等知识的讲解,以及模板代码,内容涵盖较为广泛,例题较为基础,并都有答案给出。后续还给出了三道...
一种快速素数筛法
然后,对素数的分布规律,从薛式筛法中提出数数论理论,对素数在6n+1和6n-1两列分布形式中的因子分布规律进行讨论; ,从RSA公钥密码体制着手,分析了RSA密码分析面临的诸多问题,如RSA密码分析与攻击,整数分解和...
前言在数论领域,解决问题时经常会有得到素数的需求如何快速得到一定范围内的所有素数,就成了人们一直追求的问题这里列举一些素数筛法,也许会有帮助埃氏筛法(Sieve
第一篇介绍数论中几种重要的初等方法,包括шhиpeльmah的密率论及由此发展而成的渐近密率与本性分量的理论,brun的筛法与更精密的selberg筛法,素数定理的初等证明与弱型goldbach问题的初等解法等;第二篇介绍...
暑假的时候在三体科普群里的一场讲座。做的一个简易ppt。
适合C++/C语言学习者
1. 考虑 2. 考虑 3. 考虑 1. 考虑 2. 考虑 3. 考虑
数论基础及其应用 作者:沈忠华 编著 出版时间:2015年版 内容简介 《数论基础及其应用》为数学与密码学交叉学科的特色教材,内容包括整除理论、同余、连分数、同余方程、原根。《数论基础及其应用》以数论知识为...
素数一般指质数。质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。质数只有两个正因数(1和自己)的自然数即为质数。比1大但不是素数的数称为合数。1和0既非素数也非合数。
本书为潘承洞院士写的初等数论的入门读物,每章后都有大量的习题供读者练习。
10.2 二次筛法 10.3 Pollard的P-1因子分解算法 10.4 椭圆曲线因子分解算法 10.5 数域筛法 习题十 第十一章 椭圆曲线上的离散对数 11.1 椭圆曲线公钥密码 11.2 小步-大步法 11.3 家袋鼠和野袋鼠 11.4 MOV约化 11.5 FR...
《初等数论》(第四版)(闵嗣鹤,严士健编)第一章的5个小节的练习答案:①整除的概念*带余除法,②最大公因数与辗转相除法,③整除的进一步性质及最小公倍数,④素数*算术基本定理,⑤函数[x], {x}及其在数论中的...
信奥中的数学 数论 第4讲 带余除法-2022.07.01(有作业).pdf
一-BASIC 3 IO挂 3 快速乘法 3 快速幂 3 进制转换(包括负进制)概念 3 一个数二进制1的个数 3 二-整除问题 3 整除具有的性质 3 gcd和lcm 3 一般gcd 3 快速gcd 4 ...筛素数 7 ...筛1~n的因子个数O(n) 10
希尔伯特1897年向德国数学会提交的《数论报告》用新的统一的观点,将以往代数数论的知识熔为一个整体。他抓住了互反律这个中心,利用范数剩余记号将高斯古典互反律表示成简单优美的形式: ,从而猜测到高斯互反律的...
杜教筛是一种用于解决数论问题的算法。它主要用于计算在给定区间内数的质因数个数之和。该算法的基本思想是结合了区间筛和积性函数的性质,在一定范围内高效地计算出积性函数的前缀和。 具体来说,杜教筛的步骤包括...
法兰西数学精品译丛-解析与概率数论导引(中文版)-[法]G·特伦鲍姆-陈华一(译)-高等教育出版社-2011.pdf
RothSiegel定理、A.O.关于Hilbert第七问题的证明、Siegel关于二元二次型类数的定理 关于Waring问题的证明关于问题的结果、Selberg的筛法等等;书中也包括了著者许多未经发表的结果。《华罗庚文集:数论卷2》是以深入...