Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.91/121: Рейтинг темы: голосов - 121, средняя оценка - 4.91
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19

Нахождение простых чисел на промежутке

17.11.2016, 23:01. Показов 25377. Ответов 53
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Приветствую всех.
Поиском пользовался.. т.к. только начинаю изучать с++ не могу найти ответ
подскажите пожалуйста, как оптимизировать код, что б не было лимита времени.
Задача: Вывести все простые числа от m до n включительно.Входные данные: два числа m и n (2 ≤ m ≤ n ≤ 1000000).
не проходит 2 теста - Исчерпан лимит времени.
тесты например 3 17, 2 2, 4 4
с ув.

Добавлено через 1 минуту
вот собственно код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
 
int m,n,f;
 
int main ()
{
    cin>>m>>n;
    bool x;f=0;
        for(int i=m;i<=n;i++)
        {
            x=true;
            for(int j=2;j<i;j++)
            if(i%j==0)
            {
                x=false;//f=1;
                break;
            }
            if (x)
            {
                cout<<i<<endl;
                f=1;
            }
        }
    if (f==0)
        cout<<"Absent"<<endl;
return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
17.11.2016, 23:01
Ответы с готовыми решениями:

Посчитать количество любимых простых чисел на заданном промежутке
Куратор Катя любит развлекаться с числами и цифрами. С годами работы в центре у неё появилось своё суеверие — она не любила числа, у...

Программа для поиска пар взаимно-простых натуральных чисел на определенном промежутке.
Как такое организовать? Тоесть вводишь число 5 потом 10 и программа должна найти все пары чисел у которых нод равен 1!

Нахождение простых чисел
Доброго времени суток. Помогите в написании программы,которая бы находила простые числа в пределах от 2 до 100. Зараннее благодарен.

53
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 21:26  [ТС]
Студворк — интернет-сервис помощи студентам
Ferrari F1, а вот максимально что было

код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
 
bool a[300000];
//bool a[1000000];
int m,n,f;
 
int main ()
{
    cin>>m>>n;
    
    bool x;f=0;
        
        for(int i=m;i<=n;i++)
        {
            x=true;
            for(int j=2;j<i;j++)
            if(i%j==0)
            {
                x=false;//f=1;
                break;
            }
            if (x)
            {
                cout<<i<<endl;
                f=1;
            }
            
        }
    
    if (f==0)
        cout<<"Absent"<<endl;
                
return 0;
}
Миниатюры
Нахождение простых чисел на промежутке  
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 21:30
uglubka, т.е. код Mr.X неверно вычисляет и задача еще остается нерешенной?
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 21:47  [ТС]
Я только начал изучать С++ поэтому может и дурные вопросы задаю... но интересно как оптимизировать код, что б проходило все 100% тестов. Некоторые моменты в Ваших кодах мне пока не понятны. Знаю, что мне надо сделать - пишу как умею, смотрю как люди делают - пробую.

Добавлено через 1 минуту
Ferrari F1, вот я привел скрин.. т.е. просто сделал копи-паст и отправил решени. Ниже привел код который дает самый большой результат.

Добавлено через 5 минут
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
Mr.X, а можно еще проще (думаю, что проще) поступить:
тут написано, что ограничение 64 мебибайт, что примерно равно 67 мегабайтам, так может воспользоваться этим и создать в коде массив из всех простых чисел от 2 до самого последнего простого числа, меньшего одного млна?
Такой метод использовал при решениии задачи о дружественных числах(правда на паскале) - там если делать в лоб - то проходит совсем чуть чуть - ограничения вообще минимум... т.е. надо сначала найти все такие числа, а потом просто их вбить в массив и в программе просто использовать такой масив..
Но эту задачу вроде решают без этого... ИМХО

Добавлено через 9 минут
Может нужно организовывать цикл с двух концов промежутка и проверять пока не встретятся параметры?..
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 22:05
uglubka, вот тебе такая заготовка для начала
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main()
{
    unsigned long arr[]
    {
        // вставить числа из файла сюда
    }, *beg(arr), *end(arr + sizeof arr / sizeof *arr);
 
    while (beg != end)
        cout << *beg++ << endl;
 
    system("pause");
}
Далее открываешь файл
Архив ZIP - WinRAR.zip

выделяешь весь текст(ctrl + A), копируешь(ctrl + C) и вставляешь(ctrl + V) его в район инициализации массива и отсылаешь на сервир_))
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 22:12
PS:у меня код выше с учетом вставки чисел компилировался минут 5

Добавлено через 2 минуты
Еще одна вещь: у тебя еще нужно вводить m и n, думаю сложностей не составит выполнить это условие, изменив мой код
1
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 22:52  [ТС]
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
Еще одна вещь: у тебя еще нужно вводить m и n, думаю сложностей не составит выполнить это условие, изменив мой код
может и составит... думаю видно по коду - я пока еще нульовый)) ну вот как то так.. с указателями не знаю правильно или нет

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int main()
{
    unsigned long arr[]
    {
        // вставить числа из файла сюда
    }, *beg(arr), *end(arr + sizeof arr / sizeof *arr);
 
   /////////
   long m,n;
   cin>>m>>n;
   beg=m;end=n;
   ////////
 
    while (beg != end)
        cout << *beg++ << endl;
 
    system("pause");
}
код получается содержит симолов 617221, а сайт пропускает 16384...
Миниатюры
Нахождение простых чисел на промежутке  
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 22:57
uglubka, тогда по-другому попробуем) читернем)
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
23.11.2016, 23:01
uglubka, а вы прогоняли мой код из сообщения #17?
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 23:08  [ТС]
Mr.X, погонял, может не полностью т.к. опыта маловато и знание синтаксиса пока тоже... поэтому мой код и не блещет - писал как думал (по аналогии с паскалем что ли)
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 23:11
uglubka,
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
тогда по-другому попробуем) читернем)
по другому у меня не получилось (вернее получилось, но в условие не укладывается))) Придется искать другие решения)
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
23.11.2016, 23:13
Цитата Сообщение от uglubka Посмотреть сообщение
Mr.X, погонял, может не полностью
Не, я имел в виду скопировать и запустить на вашем тесте не пробовали?
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 23:19  [ТС]
Mr.X, пробовал - просто скопировал и отправил - 7% и лимит времени по трем тестам из 15. только один десятый тест правильный...
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 23:28
Mr.X, я тоже ради интереса попробовал Ваш код из 17 поста, он валится по критерию времени...
Думаю, имеет смысл заменить битсет на булев массив(поскольку все эти вызовы методов битсета отнимают время) + еще можно все в main() затолкнуть (не вызывать функцию)
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 23:32
Mr.X, у вас все верно: 80%
по времени не проходит токо(
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 23:33  [ТС]
А можно вопрос не в тему: в какой среде лучше писать что то? dev c++ или CodeBlocks. Понимаю можете написать много вариантов, а вот из этих двух? просто когда решать на этом сайте - то только эти две среды... хотелось бы найти что то почитать как именно в этих средах отлаживать...
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 23:33
uglubka, ну мне лично visual studio 2015 удобнее
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
23.11.2016, 23:35  [ТС]
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
у вас все верно: 80%
по времени не проходит токо(
а почему у меня когда я делал копи-паст проходило только 7%.. что я не так делал?

Добавлено через 1 минуту
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
uglubka, ну мне лично visual studio 2015 удобнее
видел на скрине)
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
23.11.2016, 23:39
uglubka, потому что код Mr.X нужно было немного подкрутить: изменил на всякий случай все инициализации одиннадцатого стандарта ну и еще добавил вывод Absent, если все по нулям
0
Полярный
 Аватар для dimcoder
477 / 449 / 158
Регистрация: 11.09.2011
Сообщений: 1,156
24.11.2016, 00:23
не знаю систему работы этих тестов, но почему бы не сделать расчеты в compile-time
0
Неэпический
 Аватар для Croessmah
18150 / 10732 / 2067
Регистрация: 27.09.2012
Сообщений: 27,047
Записей в блоге: 1
24.11.2016, 00:24
Прошел все тесты:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <sstream>
 
 
int main()
{
    unsigned int m, n;
    std::cin >> m >> n;
    std::vector<char> vec(n+1, '1');
 
    for (size_t i = 3; i < vec.size(); i+=2) {
        for (size_t j = i+i; j < vec.size(); j+=i) {
            vec[j] = '0';
        }
    }
    std::stringstream ss;
 
    if (m == 2) {
        ss << 2 << '\n';
    }
    
    m += !(m&1);
    
   
    
    for (size_t i = m; i < vec.size(); i+=2){
        if ( vec[i] == '1' ) {
            ss << i << '\n';
        }
    }
    
    if (ss.str().empty()) {
        ss << "Absent";
    }
    
    std::cout << ss.str();
}
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.11.2016, 00:24

Нахождение простых чисел.(
Люди я все понимаю, этот вопрос наверное покажется глупым, точнее он таковым и является. Программа нахождения простых чисел cin...

Нахождение простых чисел в С++
Уважаемые форумчане, помогите пожалуйста сделать прогу работающей: #include&lt;iostream&gt; using namespace std; int main(){ int ...

Нахождение простых чисел
Доброго времени суток, форумчане! Написал программку, которая находит простые числа. Нормально считает где то до N=200, а после потихоньку...

Нахождение простых чисел на отрезке [m;n]
INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ 106). В выходной файл OUTPUT.TXT выведите все простые...

Нахождение простых чисел-близнецов
Программа не выдаёт правильный ответ,если добавляю строчку с else... Дано натуральное число n. Выяснить, имеются ли среди чисел n,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP
and_y87 12.10.2026
10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .
День 5 из 28: Codex подсказывает следующий запрос
and_y87 12.10.2026
9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
Adler 06.10.2026
Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru