Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 3 |
[ Сообщений: 22 ] | На страницу 1, 2, 3 След. |
|
Автор | Сообщение | |
---|---|---|
pacha |
|
|
|
||
Вернуться к началу | ||
swan |
|
|
Какого прохода?
|
||
Вернуться к началу | ||
slava_psk |
|
|
Провести последовательные целочисленные деления от 2 до n (проверяемое число) и проверять остаток.
|
||
Вернуться к началу | ||
Emphatic18 |
|
|
Если относительно просто то можно так
program massiv результат Код: 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 |
||
Вернуться к началу | ||
Tantan |
|
|
pacha писал(а): Какие есть алгоритмы? Длина массива задана. Решето Ератостена Вам известно? Если да, то : 1)задайте какого то большое [math]N >[/math] длину массива; 2) Через решето Ератостена найдите все простые чисель [math]\leqslant N[/math] и на кажды шаг следите достигли ли длину массива; 3.1) если достигли, то идите к концу алгоритма; 3.2) если не достигли длину массива, но достигли [math]N-1[/math], то увеличите горная граница цикла решето Ератостена на [math]= 2N[/math] и продолжайте от 2) дальше - [math]N+1,N+2,...,2N[/math] |
||
Вернуться к началу | ||
vorvalm |
|
|
Чтобы создать массив простых чисел до N, надо иметь
массив простых чисел до [math]\sqrt N[/math] |
||
Вернуться к началу | ||
atlakatl |
|
|
pacha писал(а): сравнить длину прохода от двух до случайно полученного числа. У простого она максимальна. Простые числа статистикой не поборешь. В любом вероятностном алгоритме будут пропуски. Обычный алгоритм, видимо, и самый быстрый: 1. Есть два простых числа: 2 и 3 (первоначальный Х) . 2. Прибавляем к Х двойку. 3. Вычисляем квадратный корень из Х. Это ограничитель на последнее простое число, делимость на которое мы проверяем. 4. Делим Х на простые, начиная с 3 до корня из шага 3. 5. Если нулевой остаток получился, то немедленное прерывание: число составное. Переход к шагу 2. 6. Если нулевого остатка не случилось, то добавляем Х в наш массив. Переход к шагу 2. |
||
Вернуться к началу | ||
Emphatic18 |
|
|
Если логическую функцию немного усложнить (как описал atlakatl), то получим приличное ускорение работы. В этом варианте определяем число на четность. Если оно четное, то сразу же говорим что оно не простое и остаток от деления перебором уже не ищем, для нечетных чисел цикл выполняется с шагом 2 начиная с попытки деления на 3.
logical function f(x) массив первых 1000 простых чисел ▼ массив
atlakatl писал(а): 4. Делим Х на простые, начиная с 3 до корня из шага 3. Хотел только уточнить, именно на простые предлагаете делить? У меня просто с шагом 2. |
||
Вернуться к началу | ||
За это сообщение пользователю Emphatic18 "Спасибо" сказали: atlakatl |
||
atlakatl |
|
|
Emphatic18 писал(а): именно на простые предлагаете делить? Цэ ж основная теорема арифметики. Если число делится на 26, то оно делится и на 2, и на 13. Обратно, если число не делится ни на 2, ни на 13, то оно не делится на 26. Ну и проверять чётные числа незачем. Просто увеличиваем очередного кандидата на 2. |
||
Вернуться к началу | ||
За это сообщение пользователю atlakatl "Спасибо" сказали: Emphatic18 |
||
Emphatic18 |
|
|
Тогда вся программа получается такой:
▼ код
результат работы тот же но в этом случае функция применима только в этой основной программе |
||
Вернуться к началу | ||
На страницу 1, 2, 3 След. | [ Сообщений: 22 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Множество простых чисел и пар простых чисел-близнецов бескон
в форуме Размышления по поводу и без |
2 |
257 |
28 июн 2023, 11:23 |
|
Дан массив целых чисел. Найти максимальное число. Сделать в
в форуме Информатика и Компьютерные науки |
0 |
641 |
29 июн 2014, 14:02 |
|
Сумма простых чисел | 15 |
222 |
28 янв 2024, 10:52 |
|
Группы простых чисел
в форуме Теория чисел |
5 |
1063 |
03 дек 2014, 15:00 |
|
Формула простых чисел?
в форуме Теория чисел |
18 |
1087 |
05 дек 2018, 21:11 |
|
Формула для простых чисел
в форуме Размышления по поводу и без |
30 |
1343 |
22 авг 2019, 23:30 |
|
Тройки простых чисел
в форуме Теория чисел |
5 |
591 |
18 июн 2018, 13:13 |
|
Свойства простых чисел
в форуме Палата №6 |
13 |
1569 |
21 июл 2016, 07:14 |
|
Формула для простых чисел
в форуме Размышления по поводу и без |
1 |
241 |
31 янв 2020, 12:22 |
|
Последовательность простых чисел
в форуме Теория чисел |
2 |
654 |
28 мар 2017, 01:43 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |