Треугольники из простых чисел и геометрические последовательности: оптимизировать код - 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
Вообщето не очень сложно, но из-за того что число большое у меня считает годами)), пробовал распаролелить, но вылетает аут оф мемори. А если мало потоков делать, то всёравно долго.
что у меня есть:
метод првоерки на простоту числа:
нахождение всех простых чисел
ну и поиск нужных элементов
Подскажите, подкиньте идейку, ка крешить эту хадачу, чтобы хотябы за сутки посчитало, а не за n лет
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; } } } } }
Решение задачи: «Треугольники из простых чисел и геометрические последовательности: оптимизировать код»
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; } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д