Задачи

Задача 3а. [1.3.2, стр.81, sumzero.c]
Нека са дадени числата a₁, a₂, ..., a_n. Да се поставят операции "+" и "-" между числата a_i  и a_i+1 за i = 1, 2,  ..., n-1 така, че резултатът след пресмятане на получения израз да бъде равен на зададено число b (1 < n < 20).

Вход:
На входа се задават редици от n + 1 числа a₁, a₂, ..., a_n, b - всяка редица на отделен ред. Всички числа са цели в интервала [1, 1000].

Изход:
За всяка редица от входа се отпечатва един израз със стойност b. Ако не може да се получи тази стойност,  да се остави празен ред.

Примерен вход:
1 1 0
1 2 3 4 5 6 7 8 0
3 4 2
30 20 40 10

Решение за примерния вход:
1-1=0
1+2+3+4-5-6-7+8=0

30+20-40=10

---

Задача 3b. Да се напише програма, която намира броя на простите числа в случайно генерирана редица.

Вход:
На стандартния вход са зададени не повече от 100 примери. Всеки пример се определя с две положителни цели числа s и N на един ред (s < 10³, N < 10⁹). s определя числова редица (чрез srand(s)) с дължина N, която се генерира с rand()%1000.

Изход:
Извежда се намерения брой - за всеки пример на отделен ред.

Пример:
25 10
102 10000

Решение на примера:
3
1616

Забележка: 0 и 1 не се броят за прости числа.
Упътване: Използвайте идеята на Решето на Ератостен. Обсъжданият в часа алгоритъм е много бавен за исканата дължина на редицата. Определянето дали числото е просто трябва да става за време O(1).

---