Решето Эратосфена через многопоточость

@OxomHuK · Регистрация: 11.07.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте! Возможно это уже и избитая тема, но не нашел подробного обьяснения или примера.
Суть - нужна программа, которая принимает 2 числа, первое - до какого числа искать простые числа, второе - количество потоков, которые устанавливаются в Executor'e.

Вот алгоритм поиска чисел(через решето Эр.)

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 public List<Integer> findPrimeNumbers1(int n) {
        if (n <= 1)
            throw new IllegalArgumentException();
        List<Integer> prime_list = new ArrayList<Integer>();
        boolean[] prime_array = new boolean[n + 1];
        Arrays.fill(prime_array, true);
 
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (prime_array[i]) {
                for (int j = i * i; j <= n; j += i) {
                    prime_array[j] = false;
                }
            }
        }
 
        for (int i = 2; i <= n; i++) {
            if (prime_array[i]) {
                prime_list.add(i);
            }
        }
        return prime_list;
    }

Буду очень признателен, если подскажете что делать дальше? как раcпаралелить поиск простых чисел, используя ThreadPool?

@агерон · 11.12.2013, 13:42

на счет много поточного поиска не могу посоветывать но могу дать совет по оптимизации проверки делителей
правда на C#

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Prime
{
    class Program
    {
        private static List<ulong> primes = new List<ulong>(new ulong[] {2}); 
        static void Main(string[] args)
        {
            Console.WriteLine("Введите предел генерации");
            var limit = Convert.ToUInt64(Console.ReadLine());
            var start = DateTime.Now.Ticks;
            for (ulong i = 3; i <= limit; i++)
            {
                var rootNumber = Convert.ToUInt64(Math.Round(Math.Sqrt(i),0));
                var flag = primes.TakeWhile(prime => prime <= rootNumber).All(prime => i%prime != 0);
                if (flag) primes.Add(i);
            }
            var end = DateTime.Now.Ticks;
            var result = new TimeSpan(end - start);
            Console.WriteLine("Генерация завершена!!!");
        }
    }
}

данный алгоритм строиться на 2 утверждениях
1) для проверки числа на простоту достаточно проверить на его делители до числа квадратного корня из числа включительно
2) любое число состоит из произведения простых чисел т. е. простые числа есть кирпичики натурального ряда
3) операясь на эти 2 определения мы можем утверждать что для того чтобы проверить является ли число простым достаточно проверить делимость проверяемого числа на все простые числа до корня квадратного из этого числа

@OxomHuK · 11.12.2013, 17:30 **[ТС]**

Сообщение от агерон

для проверки числа на простоту достаточно проверить на его делители до числа квадратного корня из числа включительно

Сообщение от OxomHuK

int i = 2; i <= Math.sqrt(n)

Не по теме:

:rofl:

Сообщение от агерон

var flag = primes.TakeWhile(prime => prime <= rootNumber).All(prime => i%prime != 0);

Не по теме:

тока лямбд мне тут не хватало

Добавлено через 56 секунд
Оптимизировать можно точно через BitSet, меня многопоточность интересует!

@агерон · 11.12.2013, 20:07

Не по теме:

OxomHuK, Вам не нравятся лямбды?:-D вы просто не умеете их готовить :-D

а если по существу то в этой программе список простых чисел выступает в качестве списка делителей числа и т. к. простые числа с каждой тысячей попадаются в принципе все реже и реже то и сложность проверки падает соответственно. Вопрос для чего нужна много поточность автору? просто для галочки или он хочет действительно во всем этом разобраться?

@OxomHuK · 12.12.2013, 06:00 **[ТС]**

Сообщение от агерон

просто для галочки

будем честными

Добавлено через 6 минут

Сообщение от агерон

то и сложность проверки падает соответственно.

всмысле!?

@агерон · 12.12.2013, 10:38

а все просто

возмем к примеру что тебе нужно проверить на простоту все числа от 4 до 1000000 в твоем алгоритме при самом грубом подсчете, с учетом того что мы проверяем в качестве делителей все числа от 2 до корня квадратного из из проверяемого числа, то под конец тебе придется проверять как делители все числа от 2 до 1000, т.е. 999 чисел для каждого из чисел близкого к миллиону.
Но если ты знаешь что любое число можно разложить на произведение простых то тебе нужно будет брать в качестве проверочных делителей только простые числа от 2 до 1000 т. е. 168 штук т. е. при этом время перебора для числа близкого к милионну, сократиться в 999/168 раза т.е примерно 5,94 раза по сравнению со стандартным алгоритмом

Добавлено через 1 минуту
для предела в 100000000 можешь посчитать сам

Добавлено через 59 минут
вот что будет если обьеденить решито эратосфена и проверку делителей

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Prime
{
    class Program
    {
        public static List<ulong> primes = new List<ulong>();
        static void Main(string[] args)
        {
            Console.WriteLine("Введите предел генерации");
            var limit = Convert.ToUInt64(Console.ReadLine());
            byte[] hash = new byte[limit + 1];
            var start = DateTime.Now.Ticks;
            for (ulong i = 2; i <= limit; i++)
                if (hash[i] == 0)
                {
                    var rootNumber = Convert.ToUInt64(Math.Round(Math.Sqrt(i), 0));
                    var flag = primes.TakeWhile(prime => prime <= rootNumber).All(prime => i%prime != 0);
                    if (!flag) continue;
                    Console.Write(" {0}",i);
                    primes.Add(i);
                    for (var j = i; j <= limit; j += i)
                        if (j == i) hash[j] = 1;
                        else hash[j] = 2;
                }
            var end = DateTime.Now.Ticks;
            var result = new TimeSpan(end - start);
            Console.WriteLine();
            Console.WriteLine("Генерация завершена!!!");
            Console.ReadLine();
        }
    }
}

@mutagen · 14.12.2013, 19:56

Комментарий модератора

ребята прекращаем кодить на шарпе или переходим на соответствующий раздел

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@агерон 447 / 300 / 65 Регистрация: 12.10.2009 Сообщений: 1,162
	11.12.2013, 20:07
	Не по теме: OxomHuK, Вам не нравятся лямбды?:-D вы просто не умеете их готовить :-D а если по существу то в этой программе список простых чисел выступает в качестве списка делителей числа и т. к. простые числа с каждой тысячей попадаются в принципе все реже и реже то и сложность проверки падает соответственно. Вопрос для чего нужна много поточность автору? просто для галочки или он хочет действительно во всем этом разобраться? 0