问题描述
Problem Description
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。
Input
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。
Output
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。
Sample Input
0 1
0 0
Sample Output
OK
问题分析
Problem Analyse
本题是为C语言初学者提供的。
Algorithm Analyse
大家还记得第2010题的算法吧？本题也一样:打表!
算法实现
首先让我们来看看这些都是什么数。
#include <stdio.h>
int main(void) {
int i, c;
for (c = 1, i = -39; i <51; i++) {
printf("%-5d", i * i + i + 41);
if (c++ % 10 == 0) putchar('\n');
}
return 0;
}
运行结果：
1523 1447 1373 1301 1231 1163 1097 1033 971 911
853 797 743 691 641 593 547 503 461 421
383 347 313 281 251 223 197 173 151 131
113 97 83 71 61 53 47 43 41 41
43 47 53 61 71 83 97 113 131 151
173 197 223 251 281 313 347 383 421 461
503 547 593 641 691 743 797 853 911 971
1033 1097 1163 1231 1301 1373 1447 1523 1601 1681
1763 1847 1933 2021 2111 2203 2297 2393 2491 2591
最大的数是2591，数据量非常小。所以判断素数的函数也不同这么花哨了。呵呵。
对刚才的代码稍作修改，就能得到其是否为素数的判断矩阵：
#include <stdio.h>
int isprime(int n) {
int i;
if (n < 2) return 0;
for (i = 2; i * i <= n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
int main(void) {
int i, c;
for (c = 1, i = -39; i <51; i++) {
printf("%-2d", isprime(i * i + i + 41));
if (c++ % 10 == 0) putchar('\n');
}
return 0;
}
运行结果：
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1
把结果保存入一个数组里，直接提交。^_^