题目代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdbool.h>

int prime[700000];
bool check[10000000];

int num = 1;

int judge(int y)
{
int p[10];
int i = 0;
for ( ; i < 10; i++) {
p[i] = -1;
}
i = 0;
while (y != 0) {
p[i] = y%10;
y /= 10;
i++;
}
int j = 0;
while(p[j] != -1)
{
j++;
}
j--;
i = 0;
while (i <= j) {
if (p[i] != p[j]) {
return 0;
}
i++,j--;
}
return 1;
}

int main()
{
int i = 2;
for ( ; i < 10000000; i++) {
if (check[i] == 0) {
prime[num++] = i;
}
int j = 1;
for ( ; j < num; j++) {
if (prime[j]*i > 10000000) {
break;
}
check[prime[j]*i] = 1;
if(i % prime[j] == 0)
break;
}
}
int a,b;
while (~scanf("%d %d", &a, &b)) {
int j;
for (j = 1; j < 10000000; j++) {
// 确定下w在prime数组里的下标
if (prime[j] >= a) {
break;
}
}
for (i = j; prime[i] <= b && i < num; i++) {
if (judge(prime[i]) == 1) { // 判断回文
printf("%d\n",prime[i]);
}
}
printf("\n");
}
return 0;
}

  1. 用prime来存储素数,但如何确定小于x范围内素数的大致个数?最简单的公式为x/lnx。但算出的结果是不准确的,大于有百分之几的误差,x越大时误差越小。
  2. 用check数组来标记所有数,初始化为0,若发现下标是合数,空间内放1;
    数组的类型可以定义为bool类型,这道题里如果是int型,空间会超,而bool类型会省很多空间,因为在32位平台c/c++,int为4字节,而bool为1字节(c语言没有bool类型,需要引头文件,c++有,无需引头文件,但无论c还是c++,大小都是1字节)。
  3. 题目给出的范围是1-100000000,但计算时看了下结果,10000000-99999999范围内没有符合的数,所以我们可以将范围缩小为原来的十分之一(可能会有别的更好地处理方法)。
  4. 素数筛法的中心模块在于以下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int i = 2;
for ( ; i < 10000000; i++) { //判断i是否为质数
if (check[i] == 0) { //说明i被小于它的所有数试除过后,标记仍为0
prime[num++] = i; //记下这个素数
}
// 无论这个数是否为素数,都将它一定范围内的倍数试除
int j = 1;
// j小于等于已有素数的下标(由于前面为num自增,所以这里不需要等号)
for ( ; j < num; j++) {
if (prime[j]*i > 10000000) {
break;
}
check[prime[j]*i] = 1;
if(i % prime[j] == 0) // 这一句很关键,解析较长写下面
break;
}
}
  • 试除法
    讲筛法前先讲下试除法…不想看的可以略过这几段…
    如果用试除法判断x是否为素数,那只需要尝试所有 小于等于 sqrt(x) 的素数即可。
    为什么要开根号很好理解,但为什么只需要尝试素数?
    例如判断101是否为素数,101开根号取整为10,小于等于10的所有素数为:2,3,5,7。
    因为所有合数都可以分解为多个素数相乘(根据欧拉函数得出的结论),例如这里的6,可以分解为2*3,这些素数必定小于这个合数,即2、3都小于6;当我们判断101是否为素数时,无需尝试它能否整除6,因为我们尝试过2和3,也就相当于尝试了6,省去对合数的尝试,可以省去不必要的重复操作。
    而 小于等于 sqrt(x) 的所有素数,在求解x前,我们都已经算出来了。因此,可以每算出一个质数,就将它保存起来(放在一个数组里)。

  • 素数筛法
    在这个基础上,如果我们将所有要判断的数放在一个容器里,每判断一个数,发现其为质数,那将它所有倍数筛去,即标记为1(容器初始化为0)。但这样又存在一个问题,例如发现3为质数,将它的15倍,即45筛去后,又发现5为质数,将他的9倍晒去,这样一来,45被重复操作,而数据较大时,会有大量的数据被重复操作。
    而前面我们提到过,每个合数由多个素数相乘,则其必有一个最小素数因子,利用这个原理,可以让每个数都被其最小素因子筛去,避免重复操作。
    又可知prime中所有素数都是递增的,当i % prime[j] == 0时,i必定可分解为prime[j]乘上另一个素数k (或i == prime[j]),k必定小于a[j++](这个简单分析下就能得出结果);例如,j=1,prime[j]=2,i=4时,i = 2*prime[j],k=2,下一个prime[j]为3,k=2<3=a[2]。后面的几组数同理。
    因此,每当 i % prime[j] == 0 时就break,因为后面的几组数里的prime[j]都不会是最小素因子。
    当避免了这些重复操作时,成为线性筛法。

  • 试除法与筛法差别
    一开始我以为两者效率会差不多,但经常时间比对发现,线性筛法比试除质数效率高很多,因为对于一些数,例如9,对9开根号为3,我们去尝试小于等于3的质数,即2、3,但是9无法被2整除,判定9为合数的关键步骤在于,9%3 = 0 ,相当于前面对2的尝试浪费了时间。
    而筛法不同,我们没有用2去判定9,而是当确定了3为素数时,直接将3的一些倍数筛去,一步到位,节省时间。


  • 以下为原题:
    #####素数回文
    xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数,请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);

Input

这里有许多组数据,每组包括两组数据a跟b。

Output

对每一组数据,按从小到大输出a,b之间所有满足条件的素数回文数(包括a跟b)每组数据之后空一行。

Sample Input

5 500

Sample Output

5
7
11
101
131
151
181
191
313
353
373
383