python どうしても競技プログラミングのD問題が解けない

Question

初心者です
[この問題](https://abc096.contest.atcoder.jp/tasks/abc096_d)に3日にほど苦しめられています
きちんと出力まではできるのですが、答えが違うと言われるばかりで、どうにも解決策が見出せません…
お時間のある方、どうか力を貸してください


```ここに言語を入力
import random
import itertools

N = int(input())

primes_list100 = []
x = 0

for i in range(2,1000):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        primes_list100.append(i)
        x += 1
        if x >=100:
            break

primes_list = random.sample(primes_list100,N)

def primes():
    primes_list = random.sample(primes_list100,N)
    return primes_list

for i in itertools.combinations(primes_list,5):
    k = sum(i)
    for j in range(2,k):
        if k%j == 0:
            break
    else:
        primes_list = primes()

print(' '.join(map(str, primes_list)))

コード
```

Accepted Answer

いや、そんなランダムにサンプル持ってきてあたればいけるはず！では解けないですよ。競プロで乱数を使うのはかなり希です(ないことはないですが、NP困難な問題を乱数をもちいて近似値を求めるというかなり難しい問題になります)。

---

では解説です。結論から言うと[Rubyでは2行](https://abc096.contest.atcoder.jp/submissions/2529379)になります。ちょっと、D問題にしては簡単すぎないかと思ったぐらいです。**気づければ**ですが。

素数同士を足したときに合成数になるパターンはどのような物かというのを考えます。

まず、`2`が含まれる場合です。`2`と4つの奇素数(奇数の素数)の和は必ず合成数になります。2の倍数個の奇数を足した場合、その数は必ず偶数です。偶数に`2`を足した場合も偶数です。そしてその数はかならず`2`より大きいですので、`2`と何らかの数を掛けた合成数になります。もう一つ重要なのは`2`以外の素数はすべて奇素数だということです。つまり、条件を満たす数列`[a_1, a_2, a_3, ...]`があれば、それに`2`を追加した`[2, a_1, a_2, a_3, ...]`も条件を満たすと言うことです。なぜなら、追加された`2`とそれ以外の素数の組合せでは、先ほどの話で全て合成数になると言うことがわかっているからです。

ということで、無条件で`2`が数列の中に追加できます。`N`個求めるという話でしたが、実際は`3`以上からなる`N-1`個の数列を見つければいいと言うことになります。これで、一個だけ最大が緩和されました。**と言いたいところですが、これは使っても使わなくてもどっちでも良いです。**それより次の方法がなかなか高速であるため、1個ぐらい多くても問題ないからです。

では、`2`以外の数を考えていきましょう。`2`の時は必ず偶数になるという組合せを考えた物でした。同じように、必ずある数の倍数になる組合せというのはあるのでしょうか？たとえば、`[3, 5, 7, 11, 13]`は3の倍数です。このとき`3`で割った余りを見てみましょう。`[0, 2, 1, 2, 1]`となりますが、これの合計も`3`の倍数です。そうです、合計がある数`X`の倍数にあるということは、`X`でそれぞれを割った余りの合計も`X`の倍数になると言うことです。しかし、`3`の場合は組合せが複雑なので、うまく求められません。では、`5`の場合は？`[1, 1, 1, 1, 1]`の合計は`5`です。きづきましたか？`5`で割った余りが`1`になる数を5つ集めれば必ず`5`になります。もしそういう数が大量にあっても、どの5個を集めても余りの合計は`5`になりますので、その数同士の和も`5`の倍数です。つまり、単純に`5`で割った余りが`1`になる数を探せば、その数同士の組合せは必ず`5`の倍数、合成数になると言うことになります。

もうおわかりですね。`5`で割った余りが`1`になる素数を単純に探していけばいいと言うことです。懸念すべきは、その素数が上限である`55555`を越えないと言うことです。ご安心ください。`55555`以下で条件を満たす素数は**1408**個もあります。この1408個の素数から、適当に`N`個取り出せば、任意の5個の和が合成数(5の倍数)になる数列ができあがると言うことです。

後は簡単ですね。`5`で割った余りが`1`になる素数を`N`個探して、それを表示するだけです。

その他のアドバイス

* Rubyは標準で素数ライブラリprimeがありますが、Pythonにはありません。Pythonで回答する場合は、自分で素数生成するコードを書く必要があります。(Rubyが2行なのはこのライブラリがあるからです)
* 素数生成のアルゴリズムはエラトステネスの篩(またはその変形)を使わないと遅いです。TLEになる場合は、素数生成のアルゴリズムを見直してください。
* 最初の`2`の話はやってもやらなくても速度はさほど変わりません。もちろん組み合わせて`N`個ではなく`N-1`個だけ求めるというのもありです。

---

書いている間に解決している…。

Answer

こんなになっちゃいました。可能な組み合わせの和の中に素数が入っていたら再サンプリングしなおしてやり直し、入っていなければbreakしてその結果を出す・・・というロジックですね。

```python
import random
import itertools

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

N = int(input())

primes_list100 = []
x = 0
for i in range(2,1000):
    if is_prime(i):
        primes_list100.append(i)
        x += 1
        if x >=100:
            break

primes_list = random.sample(primes_list100,N)
while True:
    prime_flag = False
    for combi in itertools.combinations(primes_list,5):
        combi_sum = sum(combi)
        if is_prime(combi_sum):
            prime_flag = True
            break
    if prime_flag:
        primes_list = random.sample(primes_list100,N)
    else:
        break

print(' '.join(map(str, primes_list)))
```

Nが大きくなると時間制約にひっかかると思います・・・。

### よく読まないで書いてた回答
なんでこんなの書いたんだろう・・・。
```python
for i in itertools.combinations(primes_list,5):
    k = sum(i)
    for j in range(2,k):
        if k%j == 0:
            break
    else:
        primes_list = primes()
```

よく読まないで書いてた回答

関連した質問