fork download
copy 
  1. import java.util.*;
  2. import java.util.Map.Entry;
  3.  
  4. //mevius.5ch.net/test/read.cgi/tech/1480579110/993
  5. class Q9_993
  6. {
  7.     public static void main(String[] args)
  8.     {
  9.         solve(2018);
  10.     }
  11.  
  12.     static void solve(int n)
  13.     {
  14.         if (n < 2) throw new IllegalArgumentException();
  15.  
  16.         Counter[] cs = new Counter[n + 1];
  17.         cs[0] = new Counter(true);
  18.         for (int i = 1; i < cs.length; i++)
  19.             cs[i] = new Counter(false);
  20.  
  21.         cs[2].add(cs[0]);
  22.  
  23.         for (int i = 3; i <= n; i += 2)
  24.         {
  25.             if (!isPrime(i)) continue;
  26.             for (int j = n - i; j >= 0; j--)
  27.             {
  28.                 cs[j + i].add(cs[j]);
  29.             }
  30.         }
  31.  
  32.         Entry<Integer, Long>[] result = cs[n].map.entrySet().toArray(new Entry[0]);
  33.         Arrays.sort(result, Comparator.comparingLong(Entry::getValue));
  34.  
  35.         Entry<Integer, Long> max = result[result.length - 1];
  36.         System.out.printf("最大は %d: %d%n%n", max.getKey(), max.getValue());
  37.  
  38.  
  39.         Arrays.sort(result, Comparator.comparingInt(Entry::getKey));
  40.         for (Entry<Integer, Long> e : result)
  41.             System.out.println(e);
  42.     }
  43.  
  44.     static boolean isPrime(int p)
  45.     {
  46.         if (p < 2) return false;
  47.         if ((p & 1) == 0) return p == 2;
  48.         int s = (int) Math.sqrt(p);
  49.         for (int i = 3; i <= s; i += 2)
  50.             if (p % i == 0) return false;
  51.         return true;
  52.     }
  53.  
  54.     static class Counter
  55.     {
  56.         HashMap<Integer, Long> map = new HashMap<>();
  57.  
  58.         Counter(boolean start)
  59.         {
  60.             if (start) map.put(0, 1L);
  61.         }
  62.  
  63.         void add(Counter add)
  64.         {
  65.             for (Map.Entry<Integer, Long> entry : add.map.entrySet())
  66.             {
  67.                 map.compute(entry.getKey() + 1, (k, v) -> v == null ? entry.getValue() : v + entry.getValue());
  68.             }
  69.         }
  70.     }
  71. }
  72.  
Success #stdin #stdout 0.44s 107448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
最大は 18: 9324236623725

2=27
3=73
4=85014
5=104632
6=25441718
7=26843437
8=1927081335
9=1950011652
10=51642628077
11=51553522831
12=580002627254
13=575667113960
14=3000708796948
15=2967813450808
16=7524261394862
17=7419965539959
18=9324236623725
19=9167802574632
20=5663839530138
21=5550362256900
22=1622683118072
23=1583801824431
24=202566145810
25=196670792650
26=9524805102
27=9174765695
28=127690072
29=121186234
30=259136
31=235874
32=5
33=4
https://ideone.com/DHe5Ij
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!