mountains/BeautifulMountains_artur.java
1 import java.util.ArrayList;
2 import java.util.Scanner;
3
4 public class BeautifulMountains_artur {
5 public static void main(String[] args) throws Exception {
6 Scanner in = new Scanner(System.in);
7
8 ArrayList<Integer> primes = new ArrayList<Integer>();
9 boolean[] v = new boolean[30001];
10 for (int i = 2; i < v.length; i++)
11 if (!v[i]) {
12 if (i > 2)
13 primes.add(i);
14 for (int j = i * i; j < v.length; j += i)
15 v[j] = true;
16 }
17
18 for (int n = in.nextInt(); n != 0; n = in.nextInt()) {
19 int[] a = new int[n];
20 for (int i = 0; i < n; i++)
21 a[i] = in.nextInt();
22
23 long[] l = new long[n], r = new long[n];
24 long[] lsum = new long[n], rsum = new long[n];
25 for (int i = 1, j = n - 2; i < n; i++, j--) {
26 lsum[i] = lsum[i - 1] + a[i - 1];
27 rsum[j] = rsum[j + 1] + a[j + 1];
28 l[i] = l[i - 1] + lsum[i];
29 r[j] = r[j + 1] + rsum[j];
30 }
31
32 long best = Long.MAX_VALUE;
33 for (int i = 0; i < n; i++) {
34 best = Math.min(best, l[i] + r[i]);
35 if (i + 2 < n)
36 best = Math.min(best, l[i] + r[i + 2] + a[i + 1]);
37
38 for (int p : primes) {
39 int j = i + p;
40 if (j < n) {
41 long temp = 0;
42 int k = (i + j) / 2;
43 temp += r[i] - r[k] - rsum[k] * (k - i);
44 temp += l[j] - l[k + 1] - lsum[k + 1] * (j - k - 1);
45
46 best = Math.min(best, temp + l[i] + r[j]);
47
48 if (!v[p + 2]) {
49 if (i > 1)
50 best = Math.min(best, temp + r[j] + l[i - 2] + a[i - 1]);
51 if (j < n - 2)
52 best = Math.min(best, temp + l[i] + r[j + 2] + a[j + 1]);
53 if (!v[p + 4] && i > 1 && j < n - 2)
54 best = Math.min(best, temp + l[i - 2] + r[j + 2] + a[i - 1] + a[j + 1]);
55 }
56 } else
57 break;
58 }
59 }
60 System.out.println(best);
61 }
62 }
63 }