Помогите понять эратосфен сита реализации

Question

Я нашел эту реализацию LINQ сито эратосфена на этом сайте.Я понимаю основную концепцию сита, но есть одна деталь, которую я не понимаю.Какова цель первого Enumerable.Range (0,168)?

List<int> erathostheness = Enumerable.Range(0, 168)
.Aggregate(Enumerable.Range(2, 1000000).ToList(), (result, index) =>
{
    result.RemoveAll(i => i > result[index] && i % result[index] == 0);
    return result;
}).ToList();

Answer 1

Это число раз, когда сито будет работать, чтобы исключить все не простые числа из списка.

result.RemoveAll(i => i > result[index] && i % result[index] == 0);

Каждый раз, когда вы запускаете сито, эта строка кода берет наименьшее число в списке (наименьшее простое число, из которого result еще не удалили все его множители), а затем удаляет все кратные. Это выполняется 168 раз, и в 168-й раз наименьшее число, из которого список еще не проверен, составляет 997. Это, естественно, 168-е простое число.

Это нужно выполнить только 168 раз, потому что все числа могут быть выражены как произведение списка простых чисел, и не существует числа меньше 1000000, кратного 169-му числу простых чисел (1,009), которое НЕ является кратное простому числу меньше 1009. Наименьшее число, которое можно было бы удалить путем просеивания 1009, которое НЕ было уже удалено, равно 1009 * 1013 = 1,022,117, или 169-е простые числа, умноженные на 170-е простое число, которое явно больше 100000 и, следовательно, не ' Не нужно проверять этот набор чисел.

Следовательно, все кратные 1009 уже были удалены из списка, когда вы дойдете до этой точки, поэтому нет смысла продолжать, поскольку вы уже удалили все не простые числа из списка. : D

Answer 2

Существует 168 простых чисел, меньших 1000.

Если x меньше 1,000,000, а x не простое, то x может быть разложено в простые числа p1, p2, ..., pn.По крайней мере, один из этих факторов должен быть меньше 1000, иначе продукт будет больше 1,000,000.Это означает, что хотя бы один фактор должен быть одним из первых 168 простых чисел.