|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
14.09.2022, 18:45 | #1 |
Пользователь
Регистрация: 14.09.2022
Сообщений: 24
|
Не получается найти простые сложные числа.
В общим есть задача решая которую я вошёл в тупик. "Найдите все простые числа, меньшие 𝑁. В первой строке входного файла содержатся два целых числа: 𝑁 — диапазон, в котором
нужно найти все простые числа и 𝑄 — количество запросов в файле (10 6 𝑁 6 20 000 000, 1 6 𝑄 6 200 000). В каждой из следующих 𝑄 строк содержится по одному целому числу 𝑋, для которого нужно вывести, простое оно или нет (0 6 𝑋 < 𝑁. Должно получится как я понимаю что то вот такое. Screenshot_3.png Вот написал программку Код:
|
14.09.2022, 18:50 | #2 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
А в примере еще пробелы между числом и определением not/prime
Код:
ADD: Чему изначально равно X? Значения i для линейного цикла можно предсказать, поэтому не нужно дополнительных бесполезных проверок в цикле. Т.е. можно отдельно обработать вне цикла ситуацию i == 0 и не проверять это в цикле от i = 1 до (i < N). Какой смысл в проверке Q > i, когда можно сразу вычислить E = min(N, Q); Последний раз редактировалось macomics; 14.09.2022 в 19:07. |
14.09.2022, 21:35 | #3 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,318
|
Вам нужно не счетчик цикла i проверять на простоту, а число X из файла. Поэтому и цикл нужно крутить не до N, а до Q. А каким точно образом нужно использовать N, сложно понять, так как в вашем описании задачи диапазоны плохо прописаны.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
15.09.2022, 09:08 | #4 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,566
|
Нравится мне постановка задачи: "найти простые сложные числа" . Это как "найти православных мусульман"?
А кстати - что это за "сложные числа" - это со сложной судьбой что ли? В моё студенческое время были простые и составные (но не одновременно!) . Наука, видимо, не стоит на месте... Последний раз редактировалось digitalis; 15.09.2022 в 09:13. |
15.09.2022, 15:54 | #5 | |
Пользователь
Регистрация: 14.09.2022
Сообщений: 24
|
Цитата:
|
|
15.09.2022, 16:34 | #6 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
У вас вполне ясное задание. Вы должны в диапазоне 2 .. N найти все простые числа. В условии N ограничен от 10 до 20000000, но конкретно вам это ограничение задается в первом числе файла. Q - количество последующих подстрок, в которых записаны X.
По сути задачи вам надо прости по диапазону от 2 до N (заданному) и вычислить все простые числа в этом диапазоне. После этого пройтись по файлу и считывая X (всего их Q штук) определить является ли значение простым. Т.е. 2 .. N - диапазон поиска простых чисел и значения X, заданные в файле, лежат в этом диапазоне. Но само значение N задается в диапазоне от 10 до 20000000. 1 .. Q - количество строк в файле без первой т.к. в ней заданы числа N и Q. Но само значение Q задается в диапазоне 1 .. 200000. По алгоритму. На первом этапе вы считываете N и Q. Запускаете цикл поиска простых чисел в диапазоне от 2 до N (он будет длиться по времени дольше всего) и сохраняете все простые числа в массив. После цикла поиска простых чисел вы считываете еще Q строк из файла и проверяете присутствие значения X в массиве простых чисел. Если X присутствует в массиве простых чисел, тогда выводите в выходной файл (<< X << ' prime'), иначе выводите (<< X << ' not'). Вместо массива простых чисел возможно использовать битовую карту. Это сэкономит память и ускорит второй этап проверки значений считываемых из файла. Последний раз редактировалось macomics; 15.09.2022 в 16:39. |
15.09.2022, 16:57 | #7 | |
Пользователь
Регистрация: 14.09.2022
Сообщений: 24
|
Цитата:
|
|
15.09.2022, 17:02 | #8 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
Нет. Вам задается Q чисел
INPUT: Код:
Если делать "влоб", тогда вам придется проверять 200`000 раз одни и те же числа на простоту проходя по циклу 1 .. Q ADD: Представьте себе такой входной файл Код:
Последний раз редактировалось macomics; 15.09.2022 в 17:08. |
15.09.2022, 17:11 | #9 |
Пользователь
Регистрация: 14.09.2022
Сообщений: 24
|
Понял сейчас попробую решить так задачу.
|
15.09.2022, 17:21 | #10 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
Можно кстати еще немного схитрить. Искать простые числа не в диапазоне 2 .. N, а в диапазоне 2 .. max(X).
Т.е. вводите первое X и ищите все простые числа в диапазоне 2 .. X. Считываете следующий X и если он меньше или равен предыдущему, тогда у вас уже есть массив, для ответа на вопрос о его простоте, иначе вам надо продолжить поиск простых чисел в диапазоне Xпредыдущее .. Xсчитанное. Но это и значит, что поиск простых чисел будет производиться только в диапазоне от 2 до max(X). |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
простые или сложные числа | ALUKARD_HELLSING | Общие вопросы Delphi | 10 | 31.10.2014 14:12 |
найти все простые делители числа н | keyshia_nicole | Visual C++ | 0 | 31.01.2014 18:39 |
В массиве А(100) найти простые числа. | olegk95 | Помощь студентам | 2 | 10.12.2013 09:56 |
Найти все простые числа С++ | vsubotka | Помощь студентам | 3 | 20.11.2013 12:05 |
Задачи в ТурбоПаскаль: найти числа Армстронга и просуммировать числа в последовательности номера которых простые числа | Lena1808 | Помощь студентам | 1 | 17.05.2012 08:00 |