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

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

17.11.2016, 23:01. Показов 25384. Ответов 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
24.11.2016, 00:28  [ТС]
Студворк — интернет-сервис помощи студентам
Croessmah, если не трудно можете добавить коментарии... просто интересно разобраться. спасибо
0
Неэпический
 Аватар для Croessmah
18150 / 10732 / 2067
Регистрация: 27.09.2012
Сообщений: 27,047
Записей в блоге: 1
24.11.2016, 00:50
uglubka, как Вам и советовали вначале темы,
здесь используется Решето Эратосфена (абы как).

Цитата Сообщение от uglubka Посмотреть сообщение
если не трудно можете добавить коментарии
Написюкал, не знаю насколько понятно.
Разъяснения - это не моя стихия.
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
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <sstream>
 
 
int main()
{
    unsigned int m, n;
    std::cin >> m >> n;
    //Создаем вектор размером равным n+1
    //и заполняем его единичками
    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) {//Проходим по вектору, начиная со следующего кратного i индекса с шагом i
            //и записываем в эти элементы нолики.
            //таким образом у нас получится, что мы все элементы, 
            //которые чему-либо кратны пометим этими ноликами
            vec[j] = '0';
        }
    }
    std::stringstream ss;//выводить будем изначально в строковый поток, а уже потом в cout
 
    if (m == 2) {//Если m было равно двум, то выведем двойку.
        ss << 2 << '\n';//таким образом мы обработали ситуацию, которую не учитывает алгоритм выше.
    }
    
    m += !(m&1);//если m - четное, то прибавляем 1 к нему, чтобы гарантировать его нечетность
    
   
    
    for (size_t i = m; i < vec.size(); i+=2){//теперь проходим по вектору с шагом 2, выбирая все нечетные числа
        if ( vec[i] == '1' ) {//соответственно, если индекс не кратен ничему до него, то в нем сохранится '1'
            ss << i << '\n';//значит число простое
        }
    }
    
    if (ss.str().empty()) {//Если мы ничего в поток не выводили, значит числа не найдены
        ss << "Absent";//пихаем в него "Absent", согласно условию задачи
    }
    
    std::cout << ss.str();//выводим результат
}
Всё это можно еще ускорить, как по памяти,
так и по времени, но и так всё проходит.

Добавлено через 6 минут
Собственно, переделка
C++
1
2
3
4
5
    for (size_t i = 3; i < vec.size(); i+=2) {
        for (size_t j = i+i; j < vec.size(); j+=i) {
            vec[j] = '0';
        }
    }
на
C++
1
2
3
4
5
6
7
    for (size_t i = 3; i < vec.size(); i+=2) {
        if (vec[i] != '0') {
            for (size_t j = i+i; j < vec.size(); j+=i) {
                vec[j] = '0';
            }
        }
    }
Дала время 16 ms, вместо 27.
2
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 21:21
Mr.X, я нашел проблему, по которой ваш код не проходил по времени!))
0
0 / 0 / 0
Регистрация: 17.11.2016
Сообщений: 19
24.11.2016, 21:22  [ТС]
Croessmah,
Цитата Сообщение от Croessmah Посмотреть сообщение
Разъяснения - это не моя стихия.
Я б так не сказал - очень детально и скрупулёзно.
Сам ход понятет - в принципе как Вы написали - решето.. абы как) а вот реализация некоторых моментов - надо пока матчасть почитать по самому синтаксису. Если что не разберусь - то буду спрашивать.

Уточнкение: в "переделке" ускорение за счет того, что проверяем не все елементы, а только те, которые пока равны 1?
Ну и еще сразу - "вектор" это по сути массив? Если да то инициализация пока для меня новая
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
24.11.2016, 21:23
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
Mr.X, я нашел проблему, по которой ваш код не проходил по времени!))
Интересно, и в чем же она?
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 21:23
Mr.X, виновник всему - std::endl
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
24.11.2016, 21:34
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
виновник всему - std::endl
Как лечится?
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 21:36
Mr.X, вставить "\n" ))
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
24.11.2016, 21:41
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
вставить "\n" ))
Сейчас попробовал, время то же самое.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 21:42
Цитата Сообщение от Mr.X Посмотреть сообщение
Сейчас попробовал, время то же самое.
видимо компиль на сервере не переваривает endl

Mr.X, еще надо обработать, чтоб Absent выводило) Я булев флаг вставлял
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
24.11.2016, 21:50
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
еще надо обработать, чтоб Absent выводило) Я булев флаг вставлял
Все это я вставил в вариант #17, но не ускоряется. Значит другая причина.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 22:00
Mr.X,
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//Задача: Вывести все простые числа от m до n включительно.Входные данные:
//два числа m и n (2 ≤ m ≤ n ≤ 1000000).
///////////////////////////////////////////////////////////////////////////////
#include <bitset>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
const   int     NUM_MAX{ 1000000 };
///////////////////////////////////////////////////////////////////////////////
typedef std::bitset     < NUM_MAX + 1   >   T_arr;
///////////////////////////////////////////////////////////////////////////////
void    print_prime_numbers_in_interval
(
    int     min,
    int     max
)
{
    T_arr   arr;
 
    bool flag(false);
 
    for (int i{ 2 }; i <= max; ++i)
    {
        if (
            !arr.test(i)
            )
        {
            if (i >= min)
            {
                flag = true;
                std::cout << i << '\n';
            }
 
            for (int j = i * 2; j <= max; j += i)
            {
                arr.set(j);
            }
        }
    }//for
 
    if (!flag)
        std::cout << "Absent\n";
 
    std::cout.put('\n');
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     m{};
    int     n{};
 
    std::cin >> m
        >> n;
 
    print_prime_numbers_in_interval(m, n);
}
2
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
24.11.2016, 22:02
вот кстати мое решение:
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
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    typedef unsigned long ul;
    ul m, n;
    cin >> m >> n;
 
    constexpr ul SIZE(1000000 + 1);
    vector<bool> arr(SIZE, true);
 
    ul p(2);
    for (; p < m; ++p)
        if (arr[p])
            for
            (
                unsigned long long tmp(p * p);
                tmp <= n;
                tmp += p
            )
                arr[tmp] = false;
 
    bool flag(false);
    for (; p <= n; ++p)
        if (arr[p])
        {
            flag = true;
 
            cout << p << '\n';
 
            for
            (
                unsigned long long tmp(p * p);
                tmp <= n;
                tmp += p
            )
                arr[tmp] = false;
        }
 
    if (!flag)
        cout << "Absent";
}
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
24.11.2016, 22:18
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
Mr.X,
А, да этот проходит.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.11.2016, 22:18

Нахождение простых чисел.(
Люди я все понимаю, этот вопрос наверное покажется глупым, точнее он таковым и является. Программа нахождения простых чисел 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,...


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

Или воспользуйтесь поиском по форуму:
54
Ответ Создать тему
Новые блоги и статьи
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
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. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru