Треугольники из простых чисел и геометрические последовательности: оптимизировать код - C#

Узнай цену своей работы

Формулировка задачи:

Let S(n) = a+b+c over all triples (a,b,c) such that: a, b, and c are prime numbers. a < b < c < n. a+1, b+1, and c+1 form a geometric sequence. For example, S(100) = 1035 with the following triples: (2, 5, 11), (2, 11, 47), (5, 11, 23), (5, 17, 53), (7, 11, 17), (7, 23, 71), (11, 23, 47), (17, 23, 31), (17, 41, 97), (31, 47, 71), (71, 83, 97) Find S(108). Допустим S(n) = a+b+c для все треугольников таких как: a, b, и c простые числа. a < b < c < n. a+1, b+1, и c+1 образуют геометрическую прогрессию. Например, S(100) = 1035 со следующими треугольниками: (2, 5, 11), (2, 11, 47), (5, 11, 23), (5, 17, 53), (7, 11, 17), (7, 23, 71), (11, 23, 47), (17, 23, 31), (17, 41, 97), (31, 47, 71), (71, 83, 97) Найти S(108). Источник: https://projecteuler.net/problem=518 Вообщето не очень сложно, но из-за того что число большое у меня считает годами)), пробовал распаролелить, но вылетает аут оф мемори. А если мало потоков делать, то всёравно долго. что у меня есть: метод првоерки на простоту числа:
 private static bool IsPrime(int number)
        {
            if (number == 0)
                return false;
            if (number == 1)
                return false;
            if (number == 2)
                return true;
            if (number % 2 == 0) return false;
 
            var border = Math.Sqrt(number);
            for (int i = 3; i <= border; i+=2)
            {
                if (number%i == 0) return false;
            }
            return true;
        }
нахождение всех простых чисел
 var n = 100000000;
            var threadsCount = 1000;
            long sum = 0;
            var primeValues = new List<int>();
            var threadInterval = n/threadsCount;
            var threads = new List<Thread>();
            object locker = new object();
            for (int i = 0; i < threadsCount; i++)
            {
                var thread = new Thread(_ =>
                {
                    var jStart = threadInterval*i;
                    var jEnd = threadInterval*(i + 1);
                    for (int j = jStart; j < jEnd; j++)
                    {
                        if (IsPrime(j))
                        {
                            lock (locker)
                            {
                                primeValues.Add(j);
                            }
                        }
 
                    }
                });
                threads.Add(thread);
                thread.Start();
            }
            foreach (var thread in threads)
            {
                thread.Join();
            }
ну и поиск нужных элементов
  for (int i = 0; i < primeValues.Count; i++)
            {
                for (int j = 0; j < primeValues.Count; j++)
                {
                    for (int k = 0; k < primeValues.Count; k++)
                    {
                        var a = primeValues[i];
                        var b = primeValues[j];
                        var c = primeValues[k];
                        if (a*a + b*b == c*c)
                        {
                            if ((b + 1)%(a + 1) == (c + 1)%(b + 1))
                            {
                                sum += a + b + c;
                            }
                        }
                    }
                }
            }
Подскажите, подкиньте идейку, ка крешить эту хадачу, чтобы хотябы за сутки посчитало, а не за n лет

Решение задачи: «Треугольники из простых чисел и геометрические последовательности: оптимизировать код»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
 
namespace ConsoleApplication1 {
    class Program {
        static void Main() {
            //Console.WriteLine("введите число");
            //var inp = int.Parse(Console.ReadLine());
            var inp = (int)Math.Pow(10, 2);
            var sw = new Stopwatch();
            sw.Start();
            var primeValues = new List<int>(inp / 10);
            bool[] a = PrimeNumber(inp);
            for (int i = 2; i < inp; i++) {
                if (a[i])
                    primeValues.Add(i);
            }
            sw.Stop();
            //foreach (var t in n)
            //    Console.WriteLine(t);
            Console.WriteLine(primeValues.Count);
            Console.WriteLine("Затрачено секунд {0}", (double)sw.ElapsedMilliseconds / 1000);
 
            Console.WriteLine("начало поиска треугольников");
            sw.Reset();
            sw.Start();
            Console.WriteLine();
            Console.WriteLine(primeValues.Count);
            //foreach (point p in AA(primeValues))
            //    Console.WriteLine("({0},{1},{2})", p.a, p.b, p.c);
            Console.WriteLine(Aa(primeValues));
            sw.Stop();
            Console.WriteLine("Затрачено секунд {0}", (double)sw.ElapsedMilliseconds / 1000);
            Console.ReadLine();
        }
 
        private static bool[] PrimeNumber(int number) {
            var a = new bool[number];
            for (int i = 2; i < number; i++) {
                a[i] = true;
            }
            for (int i = 2; i < Math.Sqrt(number) + 1; ++i) {
                if (a[i]) {
                    for (int j = i * i; j < number; j += i) {
                        a[j] = false;
                    }
                }
            }
            return a;
        }
        /*
        struct point {
            public int a;
            public int b;
            public int c;
            public point(int a, int b, int c)
                : this() {
                this.a = a;
                this.b = b;
                this.c = c;
            }
        }*/
 
        private static double a;
        private static int a1;
        private static long sum = 0;
 
        static /*IEnumerable<point>*/ long Aa(List<int> val) {
            long min = val.Min();
            var jj = new int[val.Count];
            val.CopyTo(jj);
            var val1 = jj.ToList();
            var ss = new Stopwatch();
            ss.Start();
            for (int i = val.Count-1; i >0; i--) {
                Writetext(String.Format("{0} осталось - предыдущий завершен за {1} секунд", i + 1, (float)ss.ElapsedMilliseconds / 1000));
                ss.Restart();
                for (int j = i -1; j >=0; j--) {
                    a = N(val[i] + 1, val[j] + 1);
                    if (a < 2){
                        break;
                    }
                    if (a%1!= 0)
                        continue;
                    a1 = (int)a;
                    if (val.Contains(a1)) {
                        sum += val[i] + val[j] + a1;
                        //yield return new point(val[i], val[j], a1);
                    }
                }
                val1.Remove(val[i]);
            }
            return sum;
        }
 
        private const int Line = 5;
 
        private static void Writetext(string i){
            Console.SetCursorPosition(0, Line);
            Console.WriteLine("                                                                     ");
            Console.SetCursorPosition(0, Line);
            Console.WriteLine(i);
        }
 
        private static double _t;
        /// <summary>
        /// 
        /// </summary>
        /// <param name="i">C</param>
        /// <param name="j">B</param>
        /// <returns></returns>
        static double N(double i, double j){
            _t = (j*j/i) - 1;
            return _t;
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4 из 5
Похожие ответы