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

@da1z · Регистрация: 03.12.2009

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

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(10⁸).

Допустим 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(10⁸).
Источник: https://projecteuler.net/problem=518
Вообщето не очень сложно, но из-за того что число большое у меня считает годами)), пробовал распаролелить, но вылетает аут оф мемори. А если мало потоков делать, то всёравно долго.
что у меня есть:
метод првоерки на простоту числа:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 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;
        }

нахождение всех простых чисел

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
 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();
            }

ну и поиск нужных элементов

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  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 лет

@Георгий713 · 04.06.2015, 11:55

da1z, есть более хорошие алгоритмы нахождения простых чисел) Решето Эратосфена, например)

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
37
38
39
40
41
42
namespace ConsoleApplication
{
    class Program
    {
        private static bool[] PrimeNumber(int number)
        {
            bool[] 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;
        }
 
        static void Main(string[] args)
        {
            Stopwatch st = new Stopwatch();
            st.Start();
            int n = 10000000;
            var primeValues = new List<int>();
            bool[] A = PrimeNumber(n);
            for (int i = 2; i < n; i++)
            {
                if (A[i])
                    primeValues.Add(i);
            }
            st.Stop();
            Console.WriteLine(st.Elapsed);
            Console.ReadLine();
        }
    }
}

Добавлено через 12 минут
Ой, я там еще 1 нолик забыл) Ну работает всё равно быстро, у меня чуть больше 9 секунд

@da1z · 04.06.2015, 12:14 **[ТС]**

Ок спасибо, у мен ябыло окло 15 секунд, но вот вторая часть вообще ад, надо её както оптимизировать)

@Георгий713 · 04.06.2015, 12:42

da1z, ну, во-первых, i<j<k, а во-вторых, если опираться на условие (геометрическая прогрессия), то условие цикла будет таким:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
            long sum = 0;
            for (int i = 0; i < primeValues.Count; i++)
            {
                for (int j = i + 1; j < primeValues.Count; j++)
                {
                    for (int k = j + 1; k < primeValues.Count; k++)
                    {
                        var a = primeValues[i];
                        var b = primeValues[j];
                        var c = primeValues[k];
                        if ((a+1)*(c+1) == (b+1)*(b+1))
                        {
                                sum += a + b + c;
                        }
                    }
                }
            }

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

@da1z · 04.06.2015, 16:39 **[ТС]**

C#
1
((a+1)*(c+1) == (b+1)*(b+1))

поясните плз? не понимаю

@KeBJIaP · 04.06.2015, 16:46

da1z, Перенос через знак равенства

@da1z · 04.06.2015, 17:01 **[ТС]**

там сравниваются остатки от деления, как эти оперции через знак равенства переносятся?

@KeBJIaP · 04.06.2015, 18:30

da1z, А да, не заметил. Все равно формула рабочая, контрольный пример проходит

Добавлено через 1 час 11 минут

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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;
        }
    }
}

Обещает считать около 300 часов) Но у меня комп слабый

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@da1z 192 / 192 / 29 Регистрация: 03.12.2009 Сообщений: 853
	04.06.2015, 12:14 [ТС]
	Ок спасибо, у мен ябыло окло 15 секунд, но вот вторая часть вообще ад, надо её както оптимизировать) 0

@KeBJIaP 146 / 143 / 32 Регистрация: 21.01.2012 Сообщений: 545
	04.06.2015, 16:46
	da1z, Перенос через знак равенства 0

@da1z 192 / 192 / 29 Регистрация: 03.12.2009 Сообщений: 853
	04.06.2015, 17:01 [ТС]
	там сравниваются остатки от деления, как эти оперции через знак равенства переносятся? 0