20200704 VillageStop

- 题目描述

有10⁸个村庄排在一条公路上，依次编号为0到10⁸-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0到an-1，其中保证a0=0。现在需要建设车站，有两个要求必须被满足：

每个有牛牛居住的村庄必须修建车站。相邻车站的距离必须为1或为某个质数。

现给出n和a数组，求需要建设车站的最小数量。

- 输入输出

输入数据包含一个数n和一个长度为n的数组a，数组a的下标为0~n-1，保证a数组递增，且a0=0。输出一个整数，表示答案。1<=n<=1000，a数组中数值保证小于10^8。

- 思路分析

任何一个偶合数可以分解为2个质数之和如果一个奇合数-2是质数，则该奇合数可以分解为2个质数和如果一个奇合数-2不是质数，则该奇合数可以分解为3个质数和

- JAVA实现

import java.util.Scanner; public class VillageStop { public static void main(String args[]) { //读取数组 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; int i = 0; while(sc.hasNextInt()) { a[i] = sc.nextInt(); i++; } System.out.println(work(n, a)); } //计算所需最小车站数 public static int work (int n, int[] a) { int min = n; for(int j=0;j+1<n;j++) { int dist = a[j+1]-a[j]; if(dist%2 == 0 & dist != 2) min++; else { if(!prime_(dist)) { if(prime_(dist-2)) min++; else min+=2; } } } return min; } //判断质数 public static boolean prime_(int dist) { if(dist == 1) return true; else { for(int i=2; i<=Math.sqrt(dist); i++) { if(dist%i == 0) return false; } return true; } } }