Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Artal98
-5 / 0 / 0
Регистрация: 09.10.2016
Сообщений: 44
1

Найти количество почти простых чисел в заданном интервале натуральных чисел.

08.10.2017, 16:02. Просмотров 604. Ответов 29
Метки нет (Все метки)

Натуральное число называется почти простым, если оно не простое и имеет только один простой делитель. Найти количество почти простых чисел в заданном интервале натуральных чисел.

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

Первая строка содержит количество тестов n (n ≤ 600). Каждая следующая строка является отдельным тестом и содержит два числа low и high (0 < low ≤ high ≤ 1012).

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

Для каждого теста вывести в отдельной строке количество почти простых чисел в промежутке [low...high] включительно.

Входные данные -
3
1 10
1 20
1 5
Выходные данные-
3
4
1
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2017, 16:02
Ответы с готовыми решениями:

Найти первые 15 натуральных чисел, делящихся нацело на d и лежащих в заданном интервале
Даны два числа d и l. Требуется найти первые 15 натуральных чисел, делящихся...

Найти количество натуральных чисел в интервале от 1 до N
Дано натуральное число N. Найти количество натуральных чисел в интервале от 1...

Найти количество чисел в интервале от 1 до N, взаимно простых с N
Дано число N. Найти количество чисел в интервале от 1 до N,взаимно простых с N.

В заданном интервале натуральных чисел определить все простые числа
из заданного интервала натуральных чисел определить все простые числа

Функция вычисления суммы квадратов простых чисел, лежащих в заданном интервале
Составить программу вычисления суммы квадратов простых чисел, лежащих в...

29
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
08.10.2017, 20:45 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using std::cin;
using std::cout;
 
bool IsPrime(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0) return false;
    }
 
    return true;
}
 
bool PrimeCom(int n)
{
    int m = 0;
    for(int i = 2; i <= n / 2; ++i)
    {
        if(n % i == 0)
        {
            if(IsPrime(i)) m++;
        }
    }
 
    if(m == 1) return true;
    else return false;
}
 
int main()
{
    const int size = 1012;
    int low, high, n;
    int mas[size];
    cin >> n;
 
    for(int i = 0; i < size; ++i) mas[i] = 0;
 
    for(int i = 0; i < n; ++i)
    {
        cin >> low >> high;
        int k = 0;
        for(int i = low; i <= high; ++i)
        {
            if(PrimeCom(i)) k++;
        }
 
        mas[i] += k;
        //if(k == 0) cout << "Absent" << std::endl;
        //else cout << k << std::endl;
    }
 
    for(int i = 0; i < n; ++i)
    {
        cout << mas[i] << std::endl;
    }
    return 0;
}
1
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 09:57 3
no swear, можно пару замечаний?
1. Не стоит в функции PrimeCom крутить цикл после того как m стало >1.
2. Легко понять, что полупростыми являются только числа вида pk, r > 1 p - простое. Учет этого факта дает довольно быстрый алгоритм даже для больших значений low
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 13:16 4
На счёт 1 согласен. На счёт второго, что то не уловил суть и для всех ли r(по моему вы имели ввиду k потому что у вас pk) это работает?
0
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 16:47 5
Цитата Сообщение от no swear Посмотреть сообщение
На счёт второго, что то не уловил суть
Это несложно доказывается математически.
Ясно, что просто простые почти простыми не являются (по определению)
Возьмем любое число и разложим его на произведение степеней простых (это можно сделать всегда)
N = p1k1*p2k2...
Если сомножителей больше одного, то число не почти простое - больше одного простого делителя.
И нам ничего не остается для почти простых, кроме N = pk (k>1)
А алгоритм такой. Просматриваем числа p до p*p < = low. Нашли простое - здорово! Для него перебирает все k от 2.
И проверяем, чтобы low <= pk <= high. Вот эти, и только они являются нам нужными.
Имхо, этот алгоритм должен быть побыстрее вашего. Хотя ваш - вполне рабочий.
Но мы же договорились, что перед лобовым решением задачи имеет смысл немножко подумать о ее математическом содержании
Особенно, когда речь идет о натуральных числах
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 18:12 6
По вашему алгоритму
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
56
57
58
#include <iostream>
#include <cmath>
using std::cin;
using std::cout;
 
bool IsPrime(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0) return false;
    }
 
    return true;
}
 
int main()
{
    const int size = 1012;
    int low, high, n, p, k, val, tmp;
    int mas[size];
    cin >> n;
 
    for(int i = 0; i < size; ++i)
    {
        mas[i] = 0;
    }
 
    for(int j = 0; j < n; ++j)
    {
        val = 0;
        cin >> low >> high;
        if(low == 1) low++;
        for(int i = 2; i <= i * i; ++i)
        {
            if(i > high) break;
            if(IsPrime(i))
            {
                p = i;
                k = 2;
                while(true)
                {
                    tmp = pow(p, k);
                    if(tmp >= low && tmp <= high) val++;
                    if(tmp > high) break;
                    k++;
                }
            }
        }
        mas[j] += val;
    }
 
    for(int i = 0; i < n; ++i)
    {
        cout << mas[i] << std::endl;
    }
 
    return 0;
}
1
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 18:22 7
no swear, не понял строчку 33
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 18:36 8
Цитата Сообщение от Байт Посмотреть сообщение
Просматриваем числа p до p*p < = low
Я не понял почему low поэтому написал high
C++
1
2
3
4
5
for(int i = 2; i <= i * i; ++i)
        {
            if(i > high) break;
            ....
        }
1
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 19:09 9
no swear, условие i <= i*i выполняется для всех i, и потому совершенно бессмысленно.
Цитата Сообщение от no swear Посмотреть сообщение
Я не понял почему low поэтому написал high
Правильное замечание. Моя ошибочка. Действительно, high
Еще не очень понятно, зачем нужен mas. Вот мы посчитали val для данным low - high. и напечатали. И все, можем о нем забыть.

Не по теме:

Сам еще помучаешься, или код набросать?:)

1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 19:38 10
Цитата Сообщение от Байт Посмотреть сообщение
Вот мы посчитали val для данным low - high. и напечатали. И все, можем о нем забыть
Согласно входным данным мы вбиваем данные в каждой строке и после этого должны получить ответ к каждой строке данных, т е сохранять по любому придётся(я так думаю)
0
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 19:43 11
А так не устроит
C++
1
2
3
4
5
6
for(int j = 0; j < n; ++j)
{
    cin >> low >> high;
    val = CalcSemiSimp(low, high);
    cout >> val << endl;
}
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 19:51 12
Так после того как мы введем low и high мы сразу будем получать ответ, а нужно чтобы после ввода всех данных выводился ответ в порядке того как мы задавали данные
1
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 19:59 13
C++
1
2
3
4
5
6
7
8
9
int CalcSemiSimp(int low, int hi) 
{  int val = 0;
  for(int p=2; p*p <=hi; p++) {
    if (!IsPrim(p) continue;
    for(int pk = p*p; pk <= hi; pk*=p)
       if (pk >= low) val++;
  }
  return val;
}
Вот в общем-то и все. Осталось собрать одеяло из лоскутков. Надеюсь, с этим ты справишься.
Не проверял. Возможны описки-ошибки. Найдешь - спасибо!

Добавлено через 6 минут
Цитата Сообщение от no swear Посмотреть сообщение
Так после того как мы введем low и high мы сразу будем получать ответ, а нужно чтобы после ввода всех данных выводился ответ в порядке того как мы задавали данные
Да, ты прав. О том, что cin дублируется в cout (эхо), я не подумал.
Ну, можно записывать в файл, а потом оттуда извлекать... Но это - те же яйца, только в профиль.
Ладно, тогда так
C++
1
2
3
4
5
for(int j = 0; j < n; ++j)
{
    cin >> low >> high;
    mas[j]l = CalcSemiSimp(low, high);
}
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 21:34 14
Окончательное решение
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
#include <iostream>
using std::cin;
using std::cout;
 
bool IsPrime(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0) return false;
    }
 
    return true;
}
 
int CalcSemiSimp(int low, int hi)
{
    int val = 0;
    for(int p=2; p*p <=hi; p++)
    {
        if (!IsPrime(p)) continue;
        for(int pk = p*p; pk <= hi; pk*=p)
        {
            if (pk >= low) val++;
        }
    }
 
  return val;
}
 
int main()
{
    const int size = 1012;
    int low, high, n, p, k, val, tmp;
    int mas[size];
    cin >> n;
 
    for(int i = 0; i < size; ++i)
    {
        mas[i] = 0;
    }
 
    for(int j = 0; j < n; ++j)
    {
        cin >> low >> high;
        mas[j] = CalcSemiSimp(low, high);
    }
 
    for(int i = 0; i < n; ++i)
    {
        cout << mas[i] << std::endl;
    }
    return 0;
}
3
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 21:41 15
no swear, Как будто все совсем хорошо.
Но, как всегда, есть пара замечаний (совсем мелких)
1. mas должен иметь размер n. Это size=1012 совершенно не в тему
2. Обнулять mas (строки 37-40) совершенно ни к чему
3. Ну и проверить неплохо бы... Может юыть при проверке и найденные числа печатать...
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 21:53 16
Цитата Сообщение от Artal98 Посмотреть сообщение
содержит два числа low и high (0 < low ≤ high ≤ 1012)
А что если 1012 это на самом деле 1012 тогда огроменное число получается.

Добавлено через 10 минут
Учёл все ваши замечания
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
56
57
58
59
60
61
62
63
#include <iostream>
using std::cin;
using std::cout;
 
bool IsPrime(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0) return false;
    }
 
    return true;
}
 
int CalcSemiSimp(int low, int hi)
{
    int val = 0;
    for(int p=2; p*p <=hi; p++)
    {
        if (!IsPrime(p)) continue;
        for(int pk = p*p; pk <= hi; pk*=p)
        {
            if (pk >= low) val++;
        }
    }
 
  return val;
}
 
int main()
{
    int low, high, n;
    cin >> n;
 
    int *mas = new int[n];
    for(int j = 0; j < n; ++j)
    {
        cin >> low >> high;
        mas[j] = CalcSemiSimp(low, high);
    }
 
    bool f = false;
    for(int i = 0; i < n; ++i)
    {
        if(mas[i])
        {
            f = true;
            break;
        }
    }
 
    if(f)
    {
        for(int i = 0; i < n; ++i)
        {
            cout << mas[i] << std::endl;
        }
    }
    else cout << "Absent";
 
    delete [] mas;
    return 0;
}
2
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 22:05 17
Цитата Сообщение от no swear Посмотреть сообщение
А что если
Вообще-то это дело ТС. Но похоже на правду. Т.к. 1012 - как-то вообще непонятно что. Но тут спасает переход к long long (64 разряда 264 > 1018)
И вот тут эффективность алгоритма становится и впрямь критичной
И тут есть еще одна лазейка для оптимизации. Совершенно не обязательно каждый раз составлять список простых чисел (а мы фактически это делаем). Можно создать его один раз для максимального high. Но вопрос - как хранить этот список, тоже ведь не маленький...
Пока писал последнюю фразу, понял, что можно построить алгоритм так, что простых чисел хранить не нужно, а просто использовать по мере появления. Но сразу во всех парах границ

Добавлено через 6 минут
Цитата Сообщение от no swear Посмотреть сообщение
Учёл все ваши замечания
Это приятно.
Но возникло еще одно. На фига здесь игры с bool f ?
Ты выясняешь, есть ли хоть в одном интервале ненулевой результат. А если нет? Просто выводим все нули, да и дело с коном!
Или я опять чего-то в условии не дочитал?
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 22:10 18
Цитата Сообщение от Байт Посмотреть сообщение
Или я опять чего-то в условии не дочитал
Как раз об этом в условии ничего не говорится, раз не говорится тогда нужно просто выводить нули в случае отсутствия таких чисел в диапазоне как вы и сказали
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>
using std::cin;
using std::cout;
 
bool IsPrime(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0) return false;
    }
 
    return true;
}
 
int CalcSemiSimp(int low, int hi)
{
    int val = 0;
    for(int p=2; p*p <=hi; p++)
    {
        if (!IsPrime(p)) continue;
        for(int pk = p*p; pk <= hi; pk*=p)
        {
            if (pk >= low) val++;
        }
    }
 
  return val;
}
 
int main()
{
    int low, high, n;
    cin >> n;
 
    int *mas = new int[n];
    for(int j = 0; j < n; ++j)
    {
        cin >> low >> high;
        mas[j] = CalcSemiSimp(low, high);
    }
 
    for(int i = 0; i < n; ++i)
    {
        cout << mas[i] << std::endl;
    }
 
    delete [] mas;
    return 0;
}
2
Байт
Эксперт C
18936 / 12154 / 2536
Регистрация: 24.12.2010
Сообщений: 24,740
09.10.2017, 22:39 19
no swear, Все. Больше замечаний нет. А то я чувствую, что своей придирчивостью тебя уже несколько утомил
1
no swear
166 / 144 / 76
Регистрация: 01.07.2016
Сообщений: 799
Завершенные тесты: 1
09.10.2017, 23:00 20
Я всегда рад учиться программированию Особенно у таких профи как вы и других пользователей этого сайта

Насчёт 1012 я завтра кину что придёт в голову
0
09.10.2017, 23:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2017, 23:00

Найти в заданном одномерном массиве количество простых чисел, используя сортировку простым включением
Помогите, пожалуйста, с решением задач. Тяжело даются динамические массивы....

Определить количество простых чисел в интервале
Определить количество простых чисел в интервале отN до M где N,M-натуальные...

Определить количество натуральных чисел на интервале
Определить количество натуральных чисел на интервале , в двоичной записи...


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

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

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