Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/15: Рейтинг темы: голосов - 15, средняя оценка - 4.60
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
1

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

03.05.2017, 19:51. Просмотров 3107. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.05.2017, 19:51
Ответы с готовыми решениями:

Выведите все "интересные" числа из отрезка [a; b] по одному в каждой строке в порядке возрастания
Теория чисел Input file: стандартный поток ввода Output file: стандартный поток вывода Time...

Вывести на экран "да", если числа имеют одинаковые знаки, в противном случае вывести "нет"
2.Даны действительные числа a и b. Вывести на экран &quot;да&quot;, если эти числа имеют одинаковые знаки, в...

Даны числа "x" и "z", если их сумма кратна 3, то вывести "1", если нет, то 0
Даны числа &quot;x&quot; и &quot;z&quot;, если их сумма кратна 3, то вывести &quot;1&quot;, если нет, то 0.

Если х равно одному из чисел N!/1, N!/2, N!/3, ...,N!/N, то вывести на экран сообщение "Да", иначе - сообщение "Нет"
Даны натуральные числа х и N(x&gt;N). Если х равно одному из чисел N!/1, N!/2, N!/3, ...,N!/N, то...

24
Почетный модератор
Эксперт по компьютерным сетямЭксперт Windows
28014 / 15740 / 971
Регистрация: 15.09.2009
Сообщений: 67,812
Записей в блоге: 78
03.05.2017, 19:57 2
может вы уже самостоятельно начнете выделять суть задачи в заголовке, а то как то стыдно должно уже быть - почти 8 сотен сообщений, почти 500 репутация, а все "ПаМаГиТе!!!"
0
1711 / 603 / 186
Регистрация: 12.03.2016
Сообщений: 2,177
03.05.2017, 20:02 3
Fixer_84, ты скидывай ссылки на задание. Так интересней, проверить себя можно. Задание ты же набрал.
0
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
03.05.2017, 20:08  [ТС] 4
мановар, Я бы с радостью, но это запрещено. Можно часть условия и фразу E-olymp вбивать - так сразу на задачу выйти можно
0
1711 / 603 / 186
Регистрация: 12.03.2016
Сообщений: 2,177
03.05.2017, 20:39 5
Fixer_84, Задание ты написал, а это ссылка на проверку (так и пиши: на проверку, а задание печатай). Ну если не разрешат, будем искать.

Добавлено через 1 минуту
Fixer_84, а ассемблерные вставки можно использовать? А распараллеливание ?

Добавлено через 21 минуту
Fixer_84, а зачем проверять на простоту четные числа? Они же явно не подходят под условие. Их нужно выкинуть из цикла (ну случай двойки предусмотреть). Да посмотреть если на конце 0 или 5, то же выкинуть. Короче, я вижу путь в этом.
0
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
03.05.2017, 21:16  [ТС] 6
мановар, да, спасибо! Я тоже уже нашел, что можно только нечетные рассматривать. Теперь попробую все это собрать и вам покажу.

Добавлено через 10 минут
мановар, сделал как вы сказали, но в 2 последних тестах все-равно не проходит по времени:

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
#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 (((i % 10 != 0) || (i % 10 != 5)) && ((i != 5) && (i != 2)))
        {
            if (simple(i))
            {
                cout << i << endl;
                k++;
            }
        }
        else if ((i == 2) || (i == 5))
        {
            cout << i << endl;
            k++;
        }
    }
    if (!(k))
        cout << "Absent" << endl;
    system("pause");
    return 0;
}
Добавлено через 18 минут
мановар, а на сайте "Дистанционная подготовка" этот код для такой же задачи прошел и все время в тестах почти по нулям Здесь, видимо, более жесткие требования...
0
1711 / 603 / 186
Регистрация: 12.03.2016
Сообщений: 2,177
03.05.2017, 21:16 7
Fixer_84, да не так. Оставьте пока в покое 0 и 5.
Вот Вам дали 1-е число допустим 15. Оно не четное, начинаем цикл с него и пошли через один

for (int i=15; i <= N; i+=2)
Т.е. на проверку потом 17, 19, 21 и т.д Там дальше посмотрим, может и пройдет. А в Ваше цикле на все условия опять все элементы проверяются, никакого отсеивания.
1
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
03.05.2017, 21:52  [ТС] 8
Цитата Сообщение от мановар Посмотреть сообщение
Fixer_84, а ассемблерные вставки можно использовать? А распараллеливание ?
Я об этом только слышал. Если смогу разберусь во всем. Надеюсь это поможет.

Добавлено через 1 минуту
Цитата Сообщение от мановар Посмотреть сообщение
Fixer_84, да не так. Оставьте пока в покое 0 и 5.
Я не сразу понял. Сейчас попробую так.

Добавлено через 28 минут
мановар, ваша идея мне ясна, но даже решето Эратосфена не помогает улучшить скорость. На другом сайте все ваши идеи проходят и скорость значительно лучше. Спасибо вам за помощь!
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.05.2017, 03:42 9
Цитата Сообщение от Fixer_84 Посмотреть сообщение
но даже решето Эратосфена не помогает улучшить скорость
Весь код, пожалста.
Решето линейное используете?
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
04.05.2017, 09:53 10
Лучший ответ Сообщение было отмечено Fixer_84 как решение

Решение

Решал когда-то уже эту задачку...
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
#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";
 
    //system("pause");
}
Вывести числа в порядке возрастания, по одному в строке. Если между M и N нет простых - вывести "Absent"
1
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.05.2017, 10:04 11
А, кстати. Если Вы все через cout выводите, то попробуйте или ios_base::sync_with_stdio(false) или printf.
Или используйте файлы
0
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
04.05.2017, 19:20  [ТС] 12
Ромаха, здравствуйте! Нашел линейный алгоритм, но не понимаю, где здесь вывод и как для интервала переделать...можете помочь?

C++
1
2
3
4
5
6
7
8
9
10
11
const int N = 10000000;
int lp[N+1];
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];
}
Вместо вектора можно использовать массив. Будет работать быстрее...

Добавлено через 2 минуты
Ferrari F1, вам большое спасибо. Вы меня просто выручили, но хотелось, конечно, разобраться во всем. Говорят решето Эратосфена с линейным временем тоже может сработать
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.05.2017, 19:26 13
Никак.
Зачем переделывать? Для каждого теста считайте до максимума, а потом идите по массиву простых чисел pr. И проверяйте, что число в диапазоне.
0
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
04.05.2017, 19:37  [ТС] 14
Не совсем понимаю...Для данного кода в интервале [2, N] где будут храниться простые числа? В pr на выходе их нет.

Добавлено через 5 минут
Ромаха, подредактировал код, чтобы вам было понятней:

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
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    int lp[N + 1];
    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];
        }
    }
    system("pause");
    return 0;
}
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
04.05.2017, 19:43 15
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Говорят решето Эратосфена с линейным временем тоже может сработать
Fixer_84, так у меня оно и так реализовано
1
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
04.05.2017, 19:45  [ТС] 16
Ferrari F1, спасибо, понял.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.05.2017, 21:23 17
Их там нет, потому что в lp мусор.
Правится вот так, например
1
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
05.05.2017, 17:25  [ТС] 18
Ромаха, спасибо Вам. Стало намного быстрее, но, все же, в последнем тесте не проходит по времени...Как, на ваш взгляд, можно еще ускорить вот этот код (мы не на [2, N], а на [M, N] рассматриваем...):

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, k;
    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];
        }
    }
    k = 0;
    for(int i = 0; i < pr.size(); i++) 
    {
        if (pr[i] >= M) 
        {
        cout << pr[i] << endl;
        k++;
        }
    }
    if (!(k)) cout << "Absent" << endl;
    system("pause");
    return 0;
}
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
05.05.2017, 18:17 19
Ага. Вот так.
Цитата Сообщение от Ромаха Посмотреть сообщение
А, кстати. Если Вы все через cout выводите, то попробуйте или ios_base::sync_with_stdio(false) или printf.
Или используйте файлы
А ускорить из-за того, что мы ищем на отрезке [m, n], а не на [1, n] нельзя (этот алгоритм)
0
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
05.05.2017, 18:38  [ТС] 20
Ромаха, Обидно. Но ведь можно как-то уменьшить размер массива и вместо вектора использовать массив или контейнером <set> (с методом find - слышал это ускоряет в разы). Также, попробую не заводить счетчик (а использовать bool) и выводить через printf()...Неужели нельзя переделать этот метод для [M, N]?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.05.2017, 18:38

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Ввести слово, вывести "ДА" если первый и последний символ совпадает, в противном случае вывести "НЕТ"
Ввести слово, вывести &quot;ДА&quot; если первый и последний символ совпадает, в противном случае вывести...

Если в строке есть хоть один ноль - вывести в файл output.txt "YES", иначе вывести "NO";
Задача. В файле input.txt содержится неприрывная строка нулей и единиц. Если в строке есть хоть...

Вывести сообщение "Есть", если в массиве присутствует ноль и "Нет", если нуля нет
Заполните массив из 10 элементов случайными числами и вывести сообщение &quot;Есть&quot;, если в массиве...

Вывести решения уравнения, если их число конечно, "NO", если решений нет, и "INF", если их бесконечно много
Задача с условным оператором. Решить в целых числах уравнение ax + b = 0. Входные данные...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.