素数を使う問題 AtCoder Beginner Contest 084 [ D - 2017-like Number ] をPythonで解く
素数系の問題っていうのがAtCoderであるみたいで、やったことないので探してやってみました。
Python ACコード
基本はまやん氏の解法のコードを元にPythonで実装しました。 blog.hamayanhamayan.com
- エラトステネスのふるいで10**5以下の素数を、あらかじめテーブル作成しておく
- 2017に似た数を判定
- 一次元累積和を使ってクエリを処理 という流れ。
検証：一次元累積和の処理いるの？
はまやんさんの解法に書いてあるから一次元累積和のコード入れましたが
「これ、本当にいるの？配列のsumとっても、そんな時間かかんないんじゃない？」
と思って、累積和の処理をはずしたコードも書いてみました。
結果：TLE
おー、ダメかー。
必要なのね。
