求素数(暴力枚举)-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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-01-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

求大于整数m且紧靠m的k个素数 及 判断一个数是否为素数的方法

题目:   请编写一个函数void fun(int m,int k ,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入xx所指的数组中。 ...

3646
来自专栏高性能服务器开发

(三)dict哈希结构3

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

2758
来自专栏HansBug's Lab

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
来自专栏猿人谷

求大于整数m且紧靠m的k个素数 及 判断一个数是否为素数的方法

题目:   请编写一个函数void fun(int m,int k ,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入xx所指的数组中。 ...

1829
来自专栏小樱的经验随笔

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

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

1996
来自专栏扎心了老铁

java优雅的使用elasticsearch api

本文给出一种优雅的拼装elasticsearch查询的方式,可能会使得使用elasticsearch的方式变得优雅起来,使得代码结构很清晰易读。 建立elast...

1K7
来自专栏码匠的流水账

聊聊storm的PartialKeyGrouping

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

1183
来自专栏码匠的流水账

聊聊spring cloud gateway的GatewayFilter

本文主要研究一下spring cloud gateway的GatewayFilter

4921
来自专栏calmound

poj 3126 Prime Path

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

2857

扫码关注云+社区

领取腾讯云代金券