# 求素数(暴力枚举)-HDU 3823

Problem Description

Besides the ordinary Boy Friend and Girl Friend, here we define a more academic kind of friend: Prime Friend. We call a nonnegative integer A is the integer B’s Prime Friend when the sum of A and B is a prime.

So an integer has many prime friends, for example, 1 has infinite prime friends: 1, 2, 4, 6, 10 and so on. This problem is very simple, given two integers A and B, find the minimum common prime friend which will make them not only become primes but also prime neighbor. We say C and D is prime neighbor only when both of them are primes and integer(s) between them is/are not.

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case only contains two integers A and B.

Technical Specification

1. 1 <= T <= 1000

2. 1 <= A, B <= 150

Output

For each test case, output the case number first, then the minimum common prime friend of A and B, if not such number exists, output -1.

Sample Input

2

2 4

3 6

Sample Output

Case 1: 1

Case 2: -1

g++:

```#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <memory.h>

/*选用20000000是因为测试数据大概在这个范围*/
const int MAX_VALUE = 2e7;
static int primes[MAX_VALUE];
static char is_prime[MAX_VALUE+1];

/*初始化一个素数表用于查询
返回数量
质数定义：在大于1的自然数中，除了1和它本身以外不再有其他因数
*/
int createPrimeTable()
{
int size = 0;
/*初始化为1*/
memset(is_prime, 1, sizeof(is_prime));

/*计算开方值*/
/*
开根号法：对大于2的数N求平方根得到S，如果N能被2-S之间的数整除，那么N不是质数
*/
int s = sqrt((double)MAX_VALUE) + 1;

/*素数的计算
双重循环：2,3,4,5...s
2,3,4,5...M/i
上下依次相乘，计算出所有结合
*/
for (int i = 2; i <= s; i++) {
if (is_prime[i]) {
/*求出最大值*/
for (int j = 2; j <= MAX_VALUE / i; j++) {
is_prime[i * j] = 0;
}
}
}
/*剩下的就是质数*/
for (int i = 2 ; i <= MAX_VALUE; i++)
if (is_prime[i])
primes[size++] = i;
/*0和1不是质数*/
is_prime[0] = is_prime[1] = 0;

return size;
}

int main()
{
int count;

scanf("%d", &count);

/*初始化素数表*/
int size = createPrimeTable();

int case_number = 1;

while (count--)
{
int a, b;
/*输入a和b*/
scanf("%d%d", &a, &b);

/*调整顺序*/
if (a > b) {
/*比较酷的方式，不用临时变量*/
a = a ^ b; b = a ^ b; a = a ^ b;
};

int prime = -1;

for (int i = 0; i < size - 1; i++)
{
/*保证a和b之间只有一个素数*/
if (primes[i] >= a && primes[i + 1] >= b)
{
/*如果恰好相等*/
if ((primes[i] - a) == (primes[i + 1] - b))
{
/*输出*/
prime = primes[i] - a;
break;
}
}
}
printf("Case %d: %d\n", case_number++, prime);
}

return 0;
}```

193 篇文章30 人订阅

0 条评论

## 相关文章

3646

### （三）dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

2758

### 3098: Hash Killer II

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

2906

### POJ 2492 A Bug's Life

A Bug's Life Time Limit: 10000MS Memory Limit: 65536K Total Submissions:...

28710

1829

### BZOJ 3097: Hash Killer I【构造题，思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

1996

1K7

### 聊聊storm的PartialKeyGrouping

storm-core-1.2.2-sources.jar!/org/apache/storm/grouping/PartialKeyGrouping.java

1183

4921

### poj 3126 Prime Path

Description ? The ministers of the cabinet were quite upset by the message from ...

2857