numbers - 素数を見つけるときにモジュロを使用する理由

Question

素数を見つけるプログラムを作成する際にモジュロ演算子が必要な理由を理解しようとしています。私は学習目的でコードを分析している学生ですが、モジュロが必要な理由について混乱しています。

Answer 1

明示的なモジュロは必要ありません。エラトステネスのふるいの実装を考えてみましょう(何かを使用するために C で):

int numbersThatMayBePrime[100];

memset(numbersThatMayBePrime, 0, sizeof(int)*100);

for(int c = 2; c < 100; c++)
{
    if(!numbersThatMayBePrime[c])
    {
        printf("%d\n", c);

        for(int strikeThrough = c; strikeThrough < 100; strikeThrough += c)
            numbersThatMayBePrime[strikeThrough] = -1;
    }
}