fork(1) download 
  1. import java.math.BigInteger;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.List;
  5. import java.util.Stack;
  6.  
  7. /*
  8. プログラミングのお題スレ Part12 
  9. //mevius.5ch.net/test/read.cgi/tech/1538096947/830
  10.  
  11. 830 名前：デフォルトの名無しさん[sage] 投稿日：2018/12/16(日) 13:54:15.20 ID:ob8ozoeg
  12. [お題] 来年と素数
  13. 今年も残りわずか、来年は2019年で平成31年。
  14.  
  15. 1)"2019"の省略形の"19"について。
  16. 　素数の和で19を作る、すべての素数配列を列挙せよ(できれば辞書順で)。
  17. 　同じ素数を何個使ってもよいが、同じ素数同士は区別しない。
  18. 　・例えば対象が"11"だと以下の6つ
  19. 　{2, 2, 2, 2, 3}
  20. 　{2, 2, 2, 5}
  21. 　{2, 2, 7}
  22. 　{2, 3, 3, 3}
  23. 　{3, 3, 5}
  24. 　{11}
  25.  
  26.  
  27. 　以下 2)3)4)は種類計のみ答える(明細は多いので略)。
  28. 2)来年の初まりは平成31年で、"31"について。
  29. 　素数の和で31を作る、その種類はいくつか。条件は1)と同様。
  30.  
  31. 3)素数の和で2019を作る、その種類はいくつか。条件は1)と同様。
  32.  
  33. 4)2019と31を続けた数 201931(=2019*100+31)について。
  34. 　素数の和で201931を作る、その種類はいくつか。
  35. 　但し、使用していい素数は31以下の素数かつ、
  36. 　同じ素数は最大2019個までしか使えない。同じ素数は区別しない。
  37.  
  38. 　※ 3)4)は64bit整数を超えるので、下10桁だけの回答も可。
  39. */
  40. class Ideone
  41. {
  42.     public static void main(String[] args)
  43.     {
  44.         solve(11);
  45.         solve(19);
  46.         solve(31);
  47.         solve(2019);
  48.         solve(201931, 31, 2019);
  49.     }
  50.  
  51.     static void solve(int n)
  52.     {
  53.         solve(n, n, n);
  54.     }
  55.  
  56.     static void solve(int n, int max, int num)
  57.     {
  58.         BigInteger[] b = new BigInteger[n + 1];
  59.         Arrays.fill(b, BigInteger.ZERO);
  60.         b[0] = BigInteger.ONE;
  61.  
  62.         for (int p = 2; p <= max; p = nextPrime(p + 1))
  63.         {
  64.             for (int i = n, j = p + p * num; i - j >= 0; i--)
  65.                 b[i] = b[i].subtract(b[i - j]);
  66.  
  67.             for (int i = p; i <= n; i++)
  68.                 b[i] = b[i].add(b[i - p]);
  69.         }
  70.  
  71.         System.out.print("N=" + n);
  72.         if (n != max) System.out.print(" 素数の最大値=" + max);
  73.         if (n != num) System.out.print(" 同じ素数の最大個数=" + num);
  74.         System.out.printf("%n=> %d%n", b[n]);
  75.  
  76.         if (b[n].compareTo(BigInteger.valueOf(100)) <= 0)
  77.         {
  78.             List<String> list = new ArrayList<>();
  79.             search(n, 0, 2, 0, max, num, new Stack<>(), list);
  80.             list.stream().forEach(System.out::println);
  81.         }
  82.  
  83.         System.out.println();
  84.     }
  85.  
  86.     static void search(int n, int cur, int p, int pn, int max, int num, Stack<Integer> stack, List<String> list)
  87.     {
  88.         if (n == cur)
  89.         {
  90.             list.add(stack.toString());
  91.             return;
  92.         }
  93.         if (cur + p <= n && pn < num)
  94.         {
  95.             stack.push(p);
  96.             search(n, cur + p, p, pn + 1, max, num, stack, list);
  97.             stack.pop();
  98.         }
  99.         p = nextPrime(p + 1);
  100.         while (cur + p <= n && p <= max)
  101.         {
  102.             stack.push(p);
  103.             search(n, cur + p, p, 1, max, num, stack, list);
  104.             stack.pop();
  105.             p = nextPrime(p + 1);
  106.         }
  107.     }
  108.  
  109.     static int nextPrime(int p)
  110.     {
  111.         if (p < 2) return 2;
  112.         p |= 1;
  113.         for (int i = 3; i * i <= p; i += 2)
  114.         {
  115.             if (p % i == 0)
  116.             {
  117.                 p += 2;
  118.                 // i = 3; // バグはここだ！(´・ω・`)
  119.                 i = 1;
  120.             }
  121.         }
  122.         return p;
  123.     }
  124. }
  125.  
Success #stdin #stdout 0.41s 2184192KB
comments (?)
stdin 
Standard input is empty
stdout 
N=11
=> 6
[2, 2, 2, 2, 3]
[2, 2, 2, 5]
[2, 2, 7]
[2, 3, 3, 3]
[3, 3, 5]
[11]

N=19
=> 23
[2, 2, 2, 2, 2, 2, 2, 2, 3]
[2, 2, 2, 2, 2, 2, 2, 5]
[2, 2, 2, 2, 2, 2, 7]
[2, 2, 2, 2, 2, 3, 3, 3]
[2, 2, 2, 2, 3, 3, 5]
[2, 2, 2, 2, 11]
[2, 2, 2, 3, 3, 7]
[2, 2, 2, 3, 5, 5]
[2, 2, 2, 13]
[2, 2, 3, 3, 3, 3, 3]
[2, 2, 3, 5, 7]
[2, 2, 5, 5, 5]
[2, 3, 3, 3, 3, 5]
[2, 3, 3, 11]
[2, 3, 7, 7]
[2, 5, 5, 7]
[2, 17]
[3, 3, 3, 3, 7]
[3, 3, 3, 5, 5]
[3, 3, 13]
[3, 5, 11]
[5, 7, 7]
[19]

N=31
=> 111

N=2019
=> 576202207044176168646563

N=201931 素数の最大値=31 同じ素数の最大個数=2019
=> 13683621769893119094927207253137
https://ideone.com/LgkDWF
お題スレ12の830
language:
Java (HotSpot 12)
created:
5 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!