Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 2 из 3 |
[ Сообщений: 22 ] | На страницу Пред. 1, 2, 3 След. |
|
Автор | Сообщение | |
---|---|---|
Emphatic18 |
|
|
▼ код
То же самое на Аде: ▼ код
Весьма интересный и строгий язык. Только из интереса (хотя это в данном случае лишнее) написал с использованием процедуры и функции, поэтому получилось длинно. К сожалению без заданного переноса строки при выводе, пока не знаю как это сделать, печатается на всю ширину консоли с автопереносом, но с заданным числом пробелов между числами. Если кто значет подскажите как сделать перенос строки при печати массива, например после 10-ти первых чисел. Вот так попроще, без лишних процедур ▼ код
|
||
Вернуться к началу | ||
slava_psk |
|
|
С++
#include <cstdlib> |
||
Вернуться к началу | ||
Emphatic18 |
|
|
slava_psk, ничего не имею против, но в Ваш код заложен очень медленный алгоритм, очень медленный. Для 100 элементного массива это не критично, но уже на 10000 это жутко медленно. Если есть желание, попробуйте вложить тот же алгоритм, который я вложил на Фортране и Аде (и о котором написал atlakatl).
ps При тестировании, дабы это не тормозило, я убрал блок кода печати: for(j=0;j<100;j++) вывел только печать одного 10000 элемента массива для контроля правильности расчета. |
||
Вернуться к началу | ||
slava_psk |
|
|
Emphatic18, а зачем вообще нужен массив из 1000 простых чисел? Какое это имеет прикладное значение? Кроме конечно, как обучение студентов циклам.
|
||
Вернуться к началу | ||
ammo77 |
|
|
запускаешь прогрессии -1+6к и 1+6к перемножаешь числа этих прогрессии на друг друга они пробегают
эти же прогрессии все числа которые не будут задеты их произведением и будут простые числа . или трудно такую программку создать |
||
Вернуться к началу | ||
atlakatl |
|
|
ammo77
Не путайте народ. Все простые числа имеют разложение [math](6n \pm 1)[/math], но не все числа этого вида простые. Можно проверять на простоту числа только этого вида, будет небольшой выигрыш в расчётах в сравнении с проверкой всех нечётных. |
||
Вернуться к началу | ||
Emphatic18 |
|
|
slava_psk писал(а): Emphatic18, а зачем вообще нужен массив из 1000 простых чисел? Какое это имеет прикладное значение? Кроме конечно, как обучение студентов циклам. В данном случае не так важно, но ведь всегда интересно реализовать именно быстрый алгоритм, это часто важно в множестве других задач, да и тем же студентам это полезно, сразу приучить писать программы, которые работают быстро. atlakatl писал(а): Все простые числа имеют разложение (6n±1) В этом случае возможны пропуски? Например выпадет какое-то число из перечня?но не все числа этого вида простые. Можно проверять на простоту числа только этого вида, будет небольшой выигрыш в расчётах в сравнении с проверкой всех нечётных. ps. Обратил внимание на алгоритмы решета Эратосфена (упоминали на прошлой странице) и решета Аткина, при желании можно попробовать, тем более на первый взгляд там возможны параллельные операции. |
||
Вернуться к началу | ||
Emphatic18 |
|
|
Алгоритм решета Эратосфена оказался весьма интересным. Суть ниже, никаких делений с остатком и все основные операции параллельны.
program eratosfen Результат Код: 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 До выжимки, сразу после того как 4 раза потрясли решето, в массиве было следующее, для наглядности: Код: 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 0 0 0 0 53 0 0 0 0 0 59 0 61 0 0 0 0 0 67 0 0 0 71 0 73 0 0 0 0 0 79 0 0 0 83 0 0 0 0 0 89 0 0 0 0 0 0 0 97 0 0 0 Отжать можно в отдельный массив, но что бы не плодить их выжал в первые 25 ячеек существующего массива. Теперь задача автоматизировать процесс, вставляя в forall нужные числа и не в ручную определять размер выжимки. program eratosfen Двумя разными алгоритмами я сформировал массив из 1 миллиона простых чисел. Для контроля правильности расчета были выведены первые 100 простых чисел, а так же последний, миллионный элемент, все сошлось один к одному. А теперь самое интересное - тестирование на скорость, ради чего и вычислялся миллионный массив (при этом машина у меня древненькая). Первый алгоритм, тот который был приведен в первом сообщении на 2-й странице, справился с задачей за 35,1 секунды, код с реализацией решета Эратосфена сделал все то же самое за 1,09 секунд, не ошибка, в 32,2 раза быстрее! При этом интересным кажется то, что с ростом величины массива разница в "разах" скорее всего будет только расти. |
||
Вернуться к началу | ||
atlakatl |
|
|
Emphatic18 писал(а): В этом случае возможны пропуски? Например выпадет какое-то число из перечня? Выпадут числа 2 и 3. Отсутствие других доказываем: 1. При делении простого числа на 6 невозможны остатки 0, 2, 4. - иначе число чётное. 2. Невозможен остаток 3 - иначе делимость на 3. 3. Остальные простые дают остатки 1 или 5. |
||
Вернуться к началу | ||
slava_psk |
|
|
Как же вам эти числа не надоели...
|
||
Вернуться к началу | ||
На страницу Пред. 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 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |