Алгоритм перебора разных комбинаций простых чисел

@4elovek37 · Регистрация: 10.10.2014

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

Доброго времени суток! Решаю разнообразные задачки по программированию, попалась вот такая:

Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.
К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.
Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1≤i≤n, 1≤k≤n. Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.

Решение я накидал, что называется, "в лоб", о чем вскоре пожалел:

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
bool P(const int n,const int k);
bool isSimple(const int val);
int S(const int n);
int main()
{
    clock_t start, end;
    start = clock();
    
    std::cout << S(10) << std::endl;
 
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double) end - start) / ((double) CLOCKS_PER_SEC));
    system("pause");
    return 0;
}
int S(const int n)
{
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            sum += P(i,j);
    return sum;
}
bool P(const int n,const int k)
{
    if (k == 0)
        return false;
    for (int i = 2; i <= n; ++i)
    {
        if(isSimple(i) == false)
            continue;
        if((n - i) == 0 && k == 1)
            return true;
        if(P(n - i, k - 1) == true)
            return true;
    }
    return false;
        
}
bool isSimple(const int a)
{
    unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}

Если при значении n в S(n) все работает прекрасно, то при увеличении n скорость вычислений падает в разы (при n = 50 я так и не дотерпел до завершения вычислений). Самой первой мыслью стало перестать в P() каждый раз заново проверять числа на isSimple(). Если мы заранее знаем наше n, можно бы сделать массив заранее отобранных простых чисел до n включительно, и работать с ним во всех итерациях.
На скорую руку накидал вот это:

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
bool P(const int n,const int k, const std::vector<int> & SimpleArr);
bool isSimple(const int val);
int S(const int n);
int main()
{
    clock_t start, end;
    start = clock();
    
    std::cout << S(10) << std::endl;
 
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double) end - start) / ((double) CLOCKS_PER_SEC));
    system("pause");
    return 0;
}
int S(const int n)
{
    int sum = 0, i;
    std::vector<int> SimpleArr;
    for (i = 1; i <=n; ++i)
        if(isSimple(i) == true)
            SimpleArr.push_back(i);
    for (i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            sum += P(i,j, SimpleArr);
    return sum;
}
bool P(const int n,const int k, const std::vector<int> & SimpleArr)
{
    if (k == 0)
        return false;
    for (int i = 0; i < SimpleArr.size(); ++i)
    {
        if((n - SimpleArr[i]) == 0 && k == 1)
            return true;
        if(P(n - SimpleArr[i], k - 1, SimpleArr) == true)
            return true;
    }
    return false;
        
}
bool isSimple(const int a)
{
    unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}

И скорость упала еще сильнее... В общем, кажется, тут нужно кардинально менять подход. Подскажите пожалуйста, в какую сторону мне лучше двигаться, что-бы оптимизировать алгоритм.

Добавлено через 13 часов 40 минут
Чуть чуть допилил, стало на ~10% быстрее, но все еще не сулит перспективы посчитать для больших чисел

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
//ТЕСТИРУЙ НА 1000!
/*
В 1930 году Шнирельман доказал, что любое целое число представимо в виде суммы не более чем 800 000 простых чисел.[8]
 
Нечётные 
В 1937 году Виноградов представил доказательство, не зависящее от справедливости гипотезы Римана, то есть доказал, 
что любое достаточно большое(???) нечётное число может быть представлено в виде суммы трёх простых. 
 
 
В 2013 году тернарная гипотеза Гольдбаха была окончательно доказана:
Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.
 
Четные
Этот результат многократно улучшался, так, в 1995 году Оливье Рамаре доказал, что любое чётное число — сумма не более чем 6 простых чисел. 
Из справедливости тернарной гипотезы Гольдбаха (доказанной в 2013 году) следует, что любое чётное число — сумма не более чем 4 простых чисел.(!!!)
 
На апрель 2012 года бинарная гипотеза Гольдбаха была проверена[9] для всех чётных чисел, не превышающих 4×1018:
Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
bool P(const int n,const int k);
bool isSimple(const int val);
int S(const int n);
int main()
{
    clock_t start, end;
    start = clock();
    
    std::cout << S(40) << std::endl;
 
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double) end - start) / ((double) CLOCKS_PER_SEC));
    system("pause");
    return 0;
}
int S(const int n)
{
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if(j == 1 && isSimple(i) == true)// для 40 и 1, 3 и 1 и тп.
                ++sum;
            else if (j != 1)
            {
                if(j > i && i / 2 < j)//для 1 и 40, 3 и 57 и т.п.
                    continue;
                else if(j == 3 && i % 2 != 0 && i > 5)//тернарная гипотеза Гольдбаха
                    ++sum;
                else if(j == 2 && i % 2 == 0 && i > 2)//бинарная гипотеза Гольдбаха
                    ++sum;
                else
                    sum += P(i,j);//Сложные вычисления, перебор всех вариантов
            }
            else 
                continue;
        }
    }
        return sum;
}
bool P(const int n,const int k)
{
    /*if (k == 0)// for 40 = ~ 37 sec
        return false;
    for (int i = n; i > 1; --i)
    {
        if(isSimple(i) == false)
            continue;
        if((n - i) == 0 && k == 1)
            return true;
        if(P(n-i, k - 1) == true)
            return true;
    }
    return false;*/
    
    if (k == 0)//for 40 = ~31 sec
        return false;
    for (int i = 2; i <= n; ++i)
    {
        if(isSimple(i) == false)
            continue;
        if((n - i) == 0 && k == 1)
            return true;
        if(P(n - i, k - 1) == true)
            return true;
    }
    return false;
        
}
bool isSimple(const int a)
{
    unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

Пытаюсь загуглить, как можно более простым способом проверить число на возможность получения его путем сложения простых цифр, но к какой-то формуле пока не пришел (за исключением прямых проверок на соответствия бинарной и тернарной теорий Гольдбаха, но это отсекает лишь часть ненужных вычислений). Задача по идее простая, а проблем почему-то очень много. У кого-нибудь есть хоть какие-то идеи?

Байт · 18.09.2016, 14:20

4elovek37, Я бы пошел таким путем.
Пусть нам надо вычислить функцию S(n) для всех n <= N
Сначала составляем список всех простых <=N p1, p2, ...
Заводим матрицу M[N, N] (по сути она битовая, но для начала можно char)
Обнуляем ее.
Теперь составляем всевозможные суммы из k=1,2, N слагаемых из этих pi (перебор можно сделать с помощью битовой шкалы) Естественно, рассматриваем суммы <= N. Пусть m - очередная такая сумма. Устанавливаем M[k,m] = 1
Дальше нам надо просто посчитать сумму единиц в соответствующем квадрате.

@4elovek37 · 18.09.2016, 15:22 **[ТС]**

Байт, хм, витало что-то такое в голове еще вчера, но почему-то ушел от этой мысли, решив что будет слишком муторно. Буду пробовать.
p.s. Как и хотел, с воем коде заменил постоянную проверку isSimple() на работу с заранее созданным массивом простых. Стало работать на ~60% быстрее, но проблему это не решило, считает все еще слишком долго. Если кому пригодится (что вряд ли), в спойлере код.

Кликните здесь для просмотра всего текста

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
//ТЕСТИРУЙ НА 1000!
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
bool P(const int n,const int k);
bool isSimple(const int val);
int S(const int n);
const int NUM = 50;
int simpleArr[NUM];
int simpleArrSize = 0;
int main()
{
    clock_t start, end;
    start = clock();
    int i, num;
    for(i = 0, num = 1 ; num <= NUM; num++)
        if(isSimple(num)) 
        {
            simpleArr[i] = num;
            //std::cout << simpleArr[i] << std::endl;
            ++i;
        }
    simpleArrSize = i;
    std::cout << S(NUM) << std::endl;
 
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double) end - start) / ((double) CLOCKS_PER_SEC));
    system("pause");
    return 0;
}
int S(const int n)
{
    int tryings = 0, badtry = 0;//for test
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j, ++tryings)//tryings - test
        {
            if(j == 1 && isSimple(i) == true)// для 40 и 1, 3 и 1 и тп.
                ++sum;
            else if (j != 1)
            {
                if(j > i && i / 2 < j)//для 1 и 40, 3 и 57 и т.п.
                    continue;
                else if(j == 3 && i % 2 != 0 && i > 5)//тернарная гипотеза Гольдбаха
                    ++sum;
                else if(j == 2 && i % 2 == 0 && i > 2)//бинарная гипотеза Гольдбаха
                    ++sum;
                else
                {
                    sum += P(i,j);//Сложные вычисления, перебор всех вариантов
                    ++badtry;
                }
            }
            else 
                continue;
        }
    }
    std::cout << "Tryings = " << tryings << ", BADTRY = " << badtry << ", GOOD TRY = " << tryings - badtry << '\n'; 
    return sum;
}
bool P(const int n,const int k)
{
    /*if (k == 0)// for 40 = ~ 37 sec
        return false;
    for (int i = n; i > 1; --i)
    {
        if(isSimple(i) == false)
            continue;
        if((n - i) == 0 && k == 1)
            return true;
        if(P(n-i, k - 1) == true)
            return true;
    }
    return false;*/
    
    if (k == 0)//for 40 = ~31 sec
        return false;
    for (int i = 0; i < simpleArrSize && simpleArr[i] <= n; ++i)
    {
        if((n - simpleArr[i]) == 0 && k == 1)
            return true;
        if(P(n - simpleArr[i], k - 1) == true)
            return true;
    }
    return false;
        
}
bool isSimple(const int a)
{
    unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

Добавлено через 8 минут
Байт,

(перебор можно сделать с помощью битовой шкалы)

А можно об этом поподробней?

Байт · 18.09.2016, 15:45

Сообщение от 4elovek37

(что вряд ли)

Почему же. Вот лично я люблю всякие теоретико-числовые задачки решать. И, думаю, я не один такой. Вот будет времечко свободное, обязательно посмотрю. Кстати, если хотите, могу вам одну подкинуть. Найти такие 6 целых положительных чисел, что сумма их 6-х степеней тоже 6-я степень. Для трех это решается в уме. Для четырех и пяти - машинным перебором. Причем для пяти результат странный. Есть четыре числа, сумма 5-х степеней которых будет 5-я степень. (Пятерки тоже есть) А вот для шести... Математическое исследование вопроса показывает, что если они и есть, то довольно велики... Если интересно - подумайте, когда будет время.

Сообщение от 4elovek37

(перебор можно сделать с помощью битовой шкалы)
А можно об этом поподробней?

Нам же нужны подмножества нашего набора простых. А подмножество описывается двоичным вектором (0 - нет элемента, 1 - есть) - битовой шкалой. Если элементов немного (<=8*size(int) = 32), то в качестве представления подмножества можно взять просто unsigned int. И перебор всех подмножеств осуществляется просто прибавлением к этому числу единички. Если больше, тут уже надо моделировать длинную арифметику. Но двоичную. И нужна всего одна операция "++". То есть штука в общем-то несложная. Представлять такие длинные числа можно char-массивом. А если памяти жалко - можно их трактовать, как последовательность битов (1 байт=8 бит) с простыми операциями - Установить n-ный бит, Проверить n-ный бит.

@4elovek37 · 18.09.2016, 16:05 **[ТС]**

От временного упадка настроения из-за собственной глупости, решил прикрутить вывод промежуточных результатов в консоль и заметил одну очень важную закономерность. Очевидно, что основную нагрузку дают вычисления при больших k, т.к. мы перебираем оочень много вариантов комбинаций простых чисел. Но начиная с k = n/2 за весь вывод программы такие проверки давали только false. Я с самого начала догадывался, что при таких "ненормальных" соотношениях маловероятны true результаты, поэтому прикрутил вот такую проверку:

C++
1
2
3
4
5
6
7
if(j == 1 && isSimple(i) == true)// для 40 и 1, 3 и 1 и тп.
                ++sum;
            else if (j != 1)
            {
                if(j > i && i / 2 < j)//для 1 и 40, 3 и 57 и т.п.
                    continue;
//и так далее

Но очевидно, что я пошел не до конца, и отрезал не все мертвые варианты. Сейчас прогоню программу подальше, что бы удостовериться в закономерности, и попробую начать резать комбинации от k = n/2. Вполне возможно, это решит проблему производительности.

@4elovek37 · 18.09.2016, 16:22 **[ТС]**

Из задачи:

S(1000) = 248838.

Таки работает, осталось понять почему

@4elovek37 · 19.09.2016, 22:41 **[ТС]**

Мне вновь не понравилось как медленно все работает, и я сел и, покопавшись в логе программы, оптимизировал алгоритм, теперь для n = 1000 считает за 0.0730 сек. Почему я так не мог сделать ранее - одному б-гу известно. Вот финальный вариант кода (решений в интернете для этой задачи нет, так что кому-то я этим могу помочь).

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
bool P(const int n,const int k);
bool isSimple(const int val);
bool inTheArr(const int val);
long long S(const int n);
const int NUM = 1000;//Искомое N
int simpleArr[NUM];
int simpleArrSize = 0;
int main()
{
    clock_t start, end;
    start = clock();
    int i, num;
    for(i = 0, num = 1 ; num <= NUM; num++)
        if(isSimple(num)) 
        {
            simpleArr[i] = num;
            ++i;
        }
    simpleArrSize = i;
    std::cout << S(NUM) << std::endl;
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double) end - start) / ((double) CLOCKS_PER_SEC));
    system("pause");
    return 0;
}
long long S(const int n)
{
    long long sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i/2; ++j)
        {
 
            if(j >= i)//для 1 и 40, 3 и 57, 3 из 3 и т.п.  
                continue;           
            if(j == 1 && !inTheArr(i))// для 40 и 1, 3 и 1 и тп.
                continue;
            if(j == 2 && i % 2 != 0)//Не подпадает под бинарную теорему Гольдбаха?
                if(!P(i, j))//Ищем комбинации
                    continue;
            ++sum;
        }
    }
    return sum;
}
bool P(const int n,const int k)
{
    if (k == 0)
        return false;
    for (int i = 0; i < simpleArrSize && simpleArr[i] <= n; ++i)
    {
        if((n - simpleArr[i]) == 0 && k == 1)
            return true;
        if(P(n - simpleArr[i], k - 1) == true)
            return true;
    }
    return false;   
}
bool inTheArr(const int val)//Проверка, простое ли число
{
    for(int i = 0; i < simpleArrSize; ++i)
        if(val == simpleArr[i])
            return true;
    return false;
}
bool isSimple(const int a)//Вызывается 1 раз за жизненный цикл программы
{
    unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

Вот лично я люблю всякие теоретико-числовые задачки решать.

Байт, к сожалению, у меня нет высшего образования (и, возможно, и не предвидится), поэтому порой при решении подобных задач я по незнанию могу пойти сложным путем и застрять там, где ВУЗовские с легкостью проходят благодаря хорошей математической базе (вероятно, этой задачкой может быть так же). Это удручает.

Байт · 20.09.2016, 12:43

Сообщение от 4elovek37

у меня нет высшего образования

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

Сообщение от 4elovek37

Почему я так не мог сделать ранее - одному б-гу известно.

Совершенно обычная ситуация. Сначала делаешь кое-как, лишь бы заработало. Ну а потом начианешь репу тереть, а потом ахаешь - какой же я был дурак! Но ведь - был

Добавлено через 12 часов 19 минут
4elovek37, посмотрел твой последний код. Впечатление самое благоприятное. Хороший рекурсивный алгоритм. Оформление грамотное. Код прозрачен, легко читается и понимается.
Пара очень мелких замечаний. Имхо, строки 39-40 можно выбросить. Также под вопросом строки 41-42.
Неоправданное использование типа long. Все твои числа с большим запасом помещаются в обычный int.
Размер массива simpleArr вполне можно взять N/2+1. Хватит навярняка.
Но это все, конечно, мелкие мелочи.
Удачи!

Добавлено через 51 минуту
4elovek37, А вот замечание уже по делу.
Тебе приходится многократно вычислять P(i, j) для одних и тех же значений аргумента. Может быть имеет смысл все таки завести матрицу char PP[N][N]. Забить ее, скажем, двойками (признак того, что значение не вычислено) И считать дальше, только если PP[i][j]==2. А как подсчитано, ставить 0 или 1 и в дальнейшем использовать.
Недостаток такого подхода - памяти много надо. Массив [1000][1000] еще ничего. Но дальше будет хуже.
Отсюда 2 выхода.
1. Хранить массив во внешней памяти (файле)
2. Создать массив PP[K][K], K < N. И брать значения из него при i, j < K. В противном случае таки считать...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
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 секунды (а то и больше),. . .

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	18.09.2016, 14:20
	4elovek37, Я бы пошел таким путем. Пусть нам надо вычислить функцию S(n) для всех n <= N Сначала составляем список всех простых <=N p1, p2, ... Заводим матрицу M[N, N] (по сути она битовая, но для начала можно char) Обнуляем ее. Теперь составляем всевозможные суммы из k=1,2, N слагаемых из этих pi (перебор можно сделать с помощью битовой шкалы) Естественно, рассматриваем суммы <= N. Пусть m - очередная такая сумма. Устанавливаем M[k,m] = 1 Дальше нам надо просто посчитать сумму единиц в соответствующем квадрате. 0