Сито Erathostenes .. найти простые числа в диапазоне. Как получить отправную точку?

Question

** ПРИМЕЧАНИЕ: это связано с заданием колледжа. Я только запрашиваю некоторые указания в правильном направлении.

У меня есть однопоточное решение для поиска простых чисел (домашнее задание - преобразовать в многопоточное решение). В настоящее время говорится, что нужно начать со списка проверяемых номеров Начиная с первого простого числа 2. (для 0 ... N).

Я хочу иметь возможность разделить список (0 ... N) на что-то вроде (0 ... 25), (26 ... 50), (51 ... 75) и (76. ..100).

Если отправной точкой для каждого списка является первое простое число. Как мне это найти? Должен ли я иметь отдельную функцию, чтобы получить это?

Спасибо.

Answer 1

Я так понимаю, что вы хотите многопоточную реализацию.Вам не нужно каждый список, чтобы начать с простого.(На самом деле это было бы немного круто, учитывая то, что вы пытаетесь вычислить.) Подумайте о группе работников, у каждого из которых есть список.Вместо того, чтобы каждый работник работал изолированно, подумайте о том, чтобы показать текущее простое число, на которое нужно просеять, и пусть каждый работник уходит и применяет его к списку этого работника.Подождите, пока каждый работник не сообщит о завершении этой фазы, найдите следующее простое число и повторите.

Answer 2

Чтобы добавить многопоточность, я бы просто использовал переменную, чтобы отследить, какое число имеет сито, и запустить поток, чтобы удалить кратные числа этих чисел.

int a = 2;
//run thread 1
while(sieve[a] == false)
    a++;
//run thread 2
//etc.

Очевидно, что есть немного больше ... но это общая идея.