Расчет простых чисел с использованием параллельных.Еогеасп


В свободное время я решил написать программу, которая бы систематически выявлять простые числа от 2 до 18,446,744,073,709,551,615. Это для забавы и обучения, как я знаю, это займет слишком много времени, чтобы вообще когда-нибудь достигнет верхнего значения, но я использую это для изучения параллельной обработки. Я знаю, что это не традиционный вопрос, но я очень хотел бы критика моих сверстников. Я знаю, что это может быть разорвана, так пожалуйста, но если вы делаете, делать это конструктивно.

Программа предназначена для запуска до тех пор, пока пользователь нажимает клавишу Esc ключ; в это время он будет генерировать файл с простыми числами обнаружил. Путь к этому файлу должен быть настроен на значение для структуры каталогов. Когда я перезапустить программу, которую он будет принимать в качестве аргумента, текст праймы файл, читая его и начиная от того, где она была прервана. Параллельная часть переработки и реализации решета для поиска простых чисел, что я был заинтересован в woodshedding.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;

namespace Prime
{
    public class Program
    {
        public static void Main(string[] args)
        {
            List<UInt64> primes = new List<UInt64>();
            primes.Add(2);
            UInt64 numberToCheck = 3;

            if (args.Count() > 0)
            {
                numberToCheck = ReadPrimesToList(args[0].ToString(), out primes) +2;
            }

            try
            {
                bool quit = false;
                Console.WriteLine("Prime Number Search");

                while (!quit)
                {
                    if (Console.KeyAvailable)
                        quit = Console.ReadKey().Key == ConsoleKey.Escape;

                    Console.Write("Processing: " + numberToCheck);

                    if (CheckForPrime(numberToCheck, primes))
                    {
                        primes.Add(numberToCheck);
                        Console.WriteLine(" Prime Found!");
                    }
                    else
                        Console.WriteLine(" Not Prime :(");

                    if (numberToCheck < UInt64.MaxValue)
                        numberToCheck+=2;
                    else
                        break;
                }

                Console.WriteLine("Exiting");
                WritePrimesToFile(primes);
                Console.WriteLine("< Press Any Key To Exit >");
                Console.ReadKey();
            }
            catch
            {
                if (primes.Count > 0)
                    WritePrimesToFile(primes);
            }
        }

        private static UInt64 ReadPrimesToList(string fileName, out List<UInt64> primes)
        {
            primes = new List<UInt64>();
            FileInfo file = new FileInfo(fileName);
            StreamReader reader = new StreamReader(file.OpenRead());

            String lineIn = String.Empty;
            while (!reader.EndOfStream)
            {
                lineIn = reader.ReadLine();
                String[] numberStrings = lineIn.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
                foreach (String numberString in numberStrings)
                {
                    primes.Add(UInt64.Parse(numberString));
                }
            }

            return primes[primes.Count() - 1];
        }

        private static void WritePrimesToFile(List<UInt64> primes)
        {
            String dateAndTime = DateTime.Now.ToString("yyyyMMddhhmm");
            String fileName = String.Format(@"<substitute your path here>\primes [{0}].txt", dateAndTime);
            FileInfo file = new FileInfo(fileName);
            using (StreamWriter writer = file.CreateText())
            {
                int maxLength = primes[primes.Count - 1].ToString().Length;

                String line = String.Empty;
                const int maxColumn = 16;
                int column = 0;


                foreach (UInt64 number in primes)
                {
                    string numberString = number.ToString();
                    int numberLength = numberString.Length;

                    line += numberString.PadLeft(maxLength, ' ') + ((column < (maxColumn-1)) ? " " : String.Empty);

                    column++;

                    if (column == maxColumn)
                    {
                        writer.WriteLine(line);
                        line = string.Empty;
                        column = 0;
                    }
                }

                if (line.Length > 0)
                    writer.WriteLine(line);

                writer.Flush();
                writer.Close();
            }
        }

        private static bool CheckForPrime(UInt64 numberToCheck, List<UInt64> primes)
        {
            if ((numberToCheck % 2) == 0)
                return false;

            UInt64 halfway = (UInt64)(Math.Ceiling((float)numberToCheck / 2F));

            bool isprime = false;
            UInt64 factor = 0;

            Parallel.ForEach<UInt64>(primes, (prime, loopState) =>
            {
                if (prime > halfway)
                {
                    isprime = true;
                    loopState.Stop();
                }

                if ((numberToCheck % prime) == 0)
                {
                    factor = prime;
                    isprime = false;
                    loopState.Stop();
                }
            });

            return (isprime && factor == 0);
        }
    }
}


6541
37
задан 17 февраля 2011 в 09:02 Источник Поделиться
Комментарии
2 ответа

Консоль.Пишу ужасно медленно. Я имею в виду это не , что плохо, но это хуже, чем можно подумать.

Попробуйте что-то вроде:

if((numberToCheck + 1) % 1000 == 0)
Console.Write("Processing: " + numberToCheck);

У меня было много случаев, когда обновление консоли, реже вылились в массовый прирост скорости. Хорошее правило Не обновлять консоль более, чем несколько раз в секунду.

21
ответ дан 2 марта 2011 в 11:03 Источник Поделиться

Хмммм... чтобы его ускорить, я хотел бы посмотреть на альтернативный простое число тестов, как тест Миллера Рабина или АКС тест

Вот пример кода для алгоритма Миллера-Рабина написанный на C#. Может быть, он может быть распараллелен и работает быстрее, чем метод в настоящее время у вас есть?

2
ответ дан 17 февраля 2011 в 09:02 Источник Поделиться