求素数(暴力枚举)-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
题意：
即求一个数，能使a，b与之相加后，成为素数，并且a与b之间没有其他的素数。
做法：
该题的关键是将20000000之前的素数打表，然后求其每个之间的差值，相等的存放到同一个数组中。
关于枚举：
如果手工都很容易算出来的东西，有理由相信写成程序以后也能很快得到结果。
枚举算法在很多时候，无法立刻得出某个问题的可行解或者最优解，但是可以用一种比较“笨”的方法通过列举所有情况然后逐一判断来得到结果，这就是枚举算法的核心思想。
枚举界法的特点是比较单纯，往往容易写出程序，也容易证明算法的正确性和分析算法的时间复杂度，可以解决一些规模很小的问題。
它的缺点是速度慢，当枚举量很大的时候运行速度无法忍受。
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;
}腾讯云开发者
