条件を満たす素数が存在すれば、それは \(10^{|S|}\) 未満です。

エラトステネスの篩により、\(N\) 以下の素数を全て列挙することは \(O(N\log\log N)\) 時間でできます。\(N\) 以下の素数の個数は \(O(N/\log N)\) 個であり、列挙した各素数に対し条件を満たすかどうか判定することは、\(\tilde{O}(|S|)\) でできることから、この問題は \(O(10^{|S|}\log|S|)\) で解くことができます。