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

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

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

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

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

Java

 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#

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#

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

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

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

@OxomHuK 31 / 31 / 6 Регистрация: 11.07.2013 Сообщений: 241
	11.12.2013, 17:30 [ТС]	3
	Сообщение от агерон для проверки числа на простоту достаточно проверить на его делители до числа квадратного корня из числа включительно Сообщение от OxomHuK int i = 2; i <= Math.sqrt(n) Не по теме: :rofl: Сообщение от агерон var flag = primes.TakeWhile(prime => prime <= rootNumber).All(prime => i%prime != 0); Не по теме: тока лямбд мне тут не хватало Добавлено через 56 секунд Оптимизировать можно точно через BitSet, меня многопоточность интересует! 0

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

@OxomHuK 31 / 31 / 6 Регистрация: 11.07.2013 Сообщений: 241
	12.12.2013, 06:00 [ТС]	5
	Сообщение от агерон просто для галочки будем честными Добавлено через 6 минут Сообщение от агерон то и сложность проверки падает соответственно. всмысле!? 0