Естествените числа се делят на прости и съставни числа. Просто число е такова естествено число чийто възможни целочислени делители са само 1 и самото число. Прости числа са: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367....
Представянето на дадено естествено число като произведение на прости множители (разлагане на число на прости делители) се нарича канонично разлагане.
Особености на прости числа са представени в хипотезите на Голдбах:
1. Всяко цяло четно число п > 2 може да се представи като сума на две прости числа. Пример: 6=3+3.
2. Всяко цяло число п> 17 може да се представи като сума на три различни прости числа. Пример: 19 = 11+5+3
3. Всяко цяло нечетно число п > 5 може да се представи като сума на три прости числа. Пример: 7 = 2+2+3
4. Всяко четно число може да се представи като разлика на две прости числа. Пример: 2 = 5-3
Съществуват различни подходи за оптимизация на алгоритъма за определяне дали дадено число е просто или съставно.
Цикълът за проверка проверка дали числото N е просто може да бъде съкратен от [2..N-1] до [2..sqr(N) - теорема на Уилсън за прости числа.
Предварително се извършва проверка за четност на числото и ако резултатът е false се проверява в цикъл с начало 3 и стъпка 2 - само числото 2 е просто, останалите четни са съставни числа. Съществува твърдение за неравномерно разпределение на последната нечетна цифра в простите числа.
Възможен е подходът жертване на памет за сметка на скорост - предварително се записват всички прости числа в желания интервал и в цикъл се проверява дали някое от тях е делител. Основание за използването му е факта, че честотата на срещане на простите числа силно намалява при увеличаване броя цифри на разглежданото число и същевременно нараства вероятността да има делител от списъка на вече откритите прости числа. Това може да се приложи само като предварителна проверка.
Да се реализира проект, чрез който се представят вътрешнопредметни връзки по Информатика.
Тема на проекта: прости и съставни числа.
Числата да се въвеждат автоматизирано (псевдослучайни числа) и/или ръчно - чрез комбинирано поле.
Да се извеждат два отделни списъка:
а) само прости числа;
б) само съставни, като се указва техния най-малък делител (2 и/или по-голям).
Реализирайте познат алгоритъм за проверка дали дадено число е просто.
Разбиването число на прости делители е в основата на използваните алгоритми за най-малко общо кратно - НОК и НОД - алгоритъм на Евклид, при автоматично генериране стойност на параметри в ред задачи като сложно тройно правило, задачи за пропорции, задачи от работа, задачи от движение и др.
В страницата прости и съставни числа са представени двойки числа 2*n-1 : 2*n+1, които са едновременно прости числа, са едновременно съставни числа или не са едновременно такива - взаимно прости.
Редицата 4, 7, 10, 12, 16, 19, 22, 24, 27, 31… съдържаща едновременно прости и съставни числа дава възможност чрез формулата:
2*n-1 да се съставя редица съдържаща само прости числа: 7, 13, 19, 23, 31, 37, 43, 47, 53, 61....
2*n+1 да се съставя редица съдържаща съставни числа: 15, 21, 25, 33, 39, 45, 49, 55, 63....
Подобен случай е и с редицата: 1, 5, 8, 11, 14, 18, 20, 23, 26, 29...
Специфичен алгоритъм за графично представяне плътност на прости числа е приложен в спирала на Ulam.
Разгледайте други реализирани примерни проекти, за които е ползвана подобна логическа структура на графичните обекти и/или приложени сходни алгоритми: прости числа, елементи в редица, съставни числа, сума от две и три прости числа, алгоритъм на Евклид, най-малко общо кратно, сложно тройно правило, пропорция / просто тройно правило, задачи от работа, задачи от движение..