Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337

Вывести числа в порядке возрастания, по одному в строке. Если между M и N нет простых - вывести "Absent"

03.05.2017, 19:51. Показов 7723. Ответов 24
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Снова всем здравствуйте! Вот до боли знакомая задача, но на промежутке функция работает не оптимально, хотя сама функция оптимизирована. 13/15 (два теста не прошли по времени). Кто-нибудь знает почему? Может быть, использовать решето Эратосфена?

Условие:

Простые числа (2)

Вывести все простые числа от M до N включительно.

Входные данные:

В первой строке находятся разделённые пробелом M и N (2 ≤ M ≤ N ≤ 1000000).

Выходные данные:

Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

Мой код:

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
#include <iostream>
#include <cmath>
 
using namespace std;
 
bool simple(int N)
{
    for (int i = 2; i <= sqrt(N); i++)
        if (N % i == 0)
            return false;
    return true;
}
 
int main()
{
    int M, N, k;
    cin >> M >> N;
    k = 0;
    for (int i = M; i <= N; i++)
    {
        if (simple(i))
        {
            cout << i << endl;
            k++;
        }
    }
    if (!(k))
        cout << "Absent" << endl;
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.05.2017, 19:51
Ответы с готовыми решениями:

Пользователь вводит два числа Определить, равны ли эти числа, и если нет, вывести их на экран в порядке возрастания
4. Пользователь вводит два числа. Определить, равны ли эти числа, и если нет, вывести их на экран в порядке возрастания.

Даны целые a,b,c. Вывести на экран нечётные числа в порядке возрастания, если же таких чисел нет, то выдать сообщение, ч
Даны целые a,b,c. Вывести на экран нечётные числа в порядке возрастания, если же таких чисел нет, то выдать сообщение, что нечётных чисел...

Вывести все цифры заданного с клавиатуры числа по одному разу в порядке их возрастания
Вывести все цифры заданного с клавиатуры числа по одному разу в порядке их возрастания. Задача на множества.

24
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
05.05.2017, 18:41
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Fixer_84 Посмотреть сообщение
и вместо вектора использовать массив
Можешь попробовать сделать reserve
Цитата Сообщение от Fixer_84 Посмотреть сообщение
контейнером <set>
Тут точно нет. Зачем тебе здесь find?
Также, попробую не заводить счетчик (а использовать bool)
Без разницы
выводить через printf()
Так сделать стоит

Добавлено через 45 секунд
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Неужели нельзя переделать этот метод для [M, N]?
Нет. Нельзя.
Посмотри на код.
Почитай e-max.
Попытайся понять почему
1
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
05.05.2017, 18:42  [ТС]
Ромаха, вы не поверите, но получилось

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
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main()
{
    int M, N;
    cin >> M >> N;
    vector<int> lp(N+1, 0);
    vector<int> pr;
    for (int i = 2; i <= N; ++i)
    {
        if (lp[i] == 0)
        {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j)
        {
            lp[i * pr[j]] = pr[j];
        }
    }
    bool p = true;
    for(int i = 0; i < pr.size(); i++) 
    {
        if (pr[i] >= M) 
        {
        printf("%d\n", pr[i]);
        p = false;
        }
    }
    if (p) cout << "Absent" << endl;
    system("pause");
    return 0;
}
Добавлено через 42 секунды
Ромаха, спасибо за помощь! Все тесты сданы!
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
05.05.2017, 18:44
Ну и прекрасно.
1
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
05.05.2017, 18:48  [ТС]
Спасибо всем огромное!
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
05.05.2017, 20:08
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Но ведь можно как-то уменьшить размер массива
в теории можно, т.к. 2 - единственное четное простое число, следовательно массив уменьшается в 2 раза
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
05.05.2017, 20:08

Вывести все числа от A до B включительно, в порядке возрастания, если A <B, или в порядке убывания в противном случае
Вариант 1 Даны два целых числа A и В (каждое в отдельной строке). Выведем все числа от A до B включительно, в порядке возрастания, если A...

Числа в строке вывести в порядке возрастания
Дана строка символов, состоящая из произвольных десятичных цифр, разделенных пробелами. Вывести на экран числа этой строки в порядке...

Вывести на экран числа в строке в порядке возрастания
Здравствуйте. Цель задания, вывести из строки, где числа разделены пробелами, эти числа в порядке возрастания. Сам по себе код вполне...

Вывести все числа между A и B включительно в порядке возрастания
Выведите на экран все числа между A и B включительно в порядке возрастания. Формат входных данных Вводятся два целых числа А и В (|А|,...

Вывести в порядке возрастания все целые числа, между A и B
Даны два целых числа A и B (A &lt; B). Вывести в порядке возрастания все целые числа, рас-положенные между A и B(в том числе A и B), a также...


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

Или воспользуйтесь поиском по форуму:
25
Ответ Создать тему
Опции темы

Новые блоги и статьи
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru