素晴らしい質問です。これはまだ多項式時間（桁数の多項式、ここでは20）であることが証明されていません—これはFinding Primes Polymathプロジェクトであり、数人の数学者（FieldsMedalistsのTerenceTaoとTimGowersを含む！）がアルゴリズムですが、プロジェクトはまだ具体的な結果を出していないようです。
とにかく、あなたができることがいくつかあります。あなたや他の人が指摘しているように、そのうちの1つは、ミラーラビンのような素数判定を使用して、各数値を試し、それが素数であるかどうかを確認することです。よく知られている数論的ヒューリスティック（素数定理に基づく）によると、nに近い数が素数である「確率」は約1 / ln（n）であるため、10 ^ 20の場合、46個の数ごとに約素数。したがって、k個の20桁の数値が必要な場合は、約50k個の数値に対してミラーラビン検定を実行します。
2番目のアプローチは、多くのA（慎重に考えていない）に対してこれを行う場合は、代わりにエラトステネスのふるいのようなふるいを使用する方が速いと思います。k個の素数が必要な場合は、約5万個（安全のためにそれ以上）の配列を作成し、それらをふるいにかけます。いくつかの数より少ない素数の事前計算されたリストから始めます。（10 10は完全に正しいですが、いくつかの合成数を許容することをいとわないので、たとえば最初の5,000万の素数によるテストなど、より小さな素数のリストで、982,451,653未満の素因数がないことを確認できます。それらの多くではありません。）
3番目のアプローチは、この問題に対する他の誰かの実装を見つけることです。:-)たとえば、番号を指定したり、次の素数を検索したり、次の10個の素数を検索したりするWebページがあります。オンラインで使用する場合は、手作業でコピーする必要があるようですが、ソースコードも利用できます。
Aより大きいすべての整数（たとえば、2と3の明らかな倍数を除く）をステップスルーして、それぞれに対して素数性テストを実行するよりも速い方法はありますか？
いいえ、素数性テストなしでは、数が素数であるかどうかを知る方法はありません。
ただし、ミラーラビンなどの確率的素数性テストを任意の数で非常に迅速に実行できます。これは、大きな素数を見つけるための安全で広く受け入れられている方法です。素数は比較的豊富であるため、この方法を使用して任意の範囲の素数を見つけるのに問題はありません。テスト済みの効率的なミラーラビン実装を使用するだけで、問題はありません。
あなたができる最善のことは、合理的な候補を生成し、それをテストすることです。Miller-Rabin検定は、数が素数である可能性が高いという要件を満たし、使用する反復回数に応じて、合成数が多かれ少なかれ任意のレベルにスリップする可能性を減らすことができます。
素数は静かな頻繁な数です。素数の頻度はlog（n）です。これは、平均して各46番目の数が素数であることを意味します（n = 10 ^ 20）。つまり、各数値の素数性をチェックすることは、そのようなオーバーヘッドではありません。