Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

итое простое число - C++

02.05.2013, 17:28. Просмотров 933. Ответов 8

Нужно найти N-ое простое число. (1 <= N <= 10^7).
Вопрос состоит в том, как эту задачу можно решать. Только блочным решетом, асимптотика O(n log ( log (n))) ??
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

По памяти должно влезть ??
Есть ли другой способ решения ?
Мой старый прекальк 10^7 простых чисел не влезает в размер решения 90 Мегабайт текста

Добавлено через 11 минут
Надеюсь, diagon, вы не пропустите этот пост мимо глаз, я надеюсь на вас
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2013, 17:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос итое простое число (C++):

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число - C++
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число. - C++
6.2.2. Помогите, пожалуйста, решить задачи в С++ с помощью функций. Дано простое число. Составить функцию, которая будет находить...

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число - C++
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.

Дано простое число. Составить функцию,которая будет находить следующее за ним простое число. - C++
дано простое число.составить функцию,которая будет находить следующее за ним простое число.

Дано натуральное число. Найти ближайшее простое число - C++
1. Дано натуральное число. Найти ближайшее простое число. 2. Дано 20 пар однозначных чисел. Первое число каждой пары означает количество...

Передать в функцию целое число. Функция заменяет его на ближайшее простое число, которое больше или меньше исходного. Вернуться в main( ) и распечатат - C++
Передать в функцию целое число. Функция заменяет его на ближайшее простое число, которое больше или меньше исходного. Вернуться в main( ) и...

8
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.05.2013, 19:02 #2
Цитата Сообщение от Ternsip Посмотреть сообщение
По памяти должно влезть ??
Разумеется, там же потребуется хранить простые числа до корня (а их можно хранить очень компактно, тратя один байт на каждое простое число) + константа на блок.

А вот со временем ситуация несколько иная - если вы реализуете блочное решето достаточно хорошо (а это непросто), то оно будет работать не более секунды. То есть если реализуете в лоб, то оно не пройдет по времени.

Цитата Сообщение от Ternsip Посмотреть сообщение
Есть ли другой способ решения ?
Есть, можно примерно вычислить значение (например через Riemann's R) и затем уточнить его, используя PI(x). Это гораздо эффективнее, но сложнее в теории и реализации. Проще накодить блочное решето.
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 19:14  [ТС] #3
diagon, мда, я посмотрел, наверное я блочное решето замучу Спасибо.
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
02.05.2013, 20:05 #4
Цитата Сообщение от Ternsip Посмотреть сообщение
Вопрос состоит в том, как эту задачу можно решать. Только блочным решетом, асимптотика O(n log ( log (n))) ??
позволю себе дерзость ответить... науке известны алгоритмы с асимптотикой O(N / (log log N)) и O(N^(1/2)) памяти...

Добавлено через 4 минуты
еще позволю себе отметить, что в блочном решете важна степень прекалка. при большом предпосчете блочное решето, действительно, очень быстрое...
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.05.2013, 20:09 #5
Цитата Сообщение от salam Посмотреть сообщение
науке известны алгоритмы с асимптотикой O(N / (log log N)) и O(N^(1/2)) памяти...
И при этом с гораздо большей константой. Оптимизированное решето Эратосфена быстрее решета Аткина в разы.
Оба алгоритма отличаются на http://www.cyberforum.ru/cgi-bin/latex.cgi?{(\log{\log{n}})}^{2}, а это очень мелкая величина. К тому же, за счет wheel factorization можно добиться линейной сложности у решета Эратосфена.
Но, несмотря на проигрыш в ассимптотике, блочное решето Эратосфена гораздо более эффективно использует кеш и, следовательно, имеет сильно меньшую константу.
1
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
02.05.2013, 20:31 #6
разговор, помнится, был об асимптотике, потому собственно говоря... линейное решето не стал упоминать по понятным всем причинам. на счет эффективности блочного решета никто не спорил вроде...
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.05.2013, 18:26  [ТС] #7
Блочное решето с модификациями прошло.
Вот код, кстати его легко использовать для генерации простых чисел, работает, конечно, ещё быстрее, чем если бы каждое по-отдельности проверять.
Тему можно считать закрытой.
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
const int sqrt_maxn = 100000;
const int S = 10000;
bool nprime[sqrt_maxn], bl[S];
int primes[sqrt_maxn], cnt;
 
int main() {                
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int idx;
    cin >> idx;
    int n = 179424673; // 10^7 prime number 
    int nsqrt = (int) sqrt ((double)n);
    for (int i = 2; i <= nsqrt; ++i) {
        if (!nprime[i]) {
            primes[cnt++] = i;
            if (i * 1ll * i <= nsqrt)
                for (int j = i * i; j <= nsqrt; j += i)
                    nprime[j] = true;
        }
    }
    int result = 0;
    for (int k = 0, maxk = n/S; k <= maxk; ++k) {
        memset (bl, 0, sizeof bl);
        int start = k * S;
        for (int i = 0; i < cnt; ++i) {
            for (int j = max((start + primes[i] - 1) / primes[i], 2) * primes[i] - start; j < S; j += primes[i]) {
                bl[j] = true;
            }
        }
        if (k == 0)
            bl[0] = bl[1] = true;
        for (int i = 0; i < S && start + i <= n; ++i) {
            if (!bl[i]) {
                ++result;
                if (result == idx) {
                    cout << i + k * S;
                    return 0;
                }
            }
        }
    }
    return 0;
}
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
07.05.2013, 18:28 #8
будьте любезны ссылочку на задачу и время вашего сабмита.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.05.2013, 18:34  [ТС] #9
salam, http://acm.sgu.ru/univer боюсь вам туда доступ будет закрыт, заходить можно из Саратова или Энгельса. работает за 1000 ms ровно на самом жутком тесте. Попробуйте proxy. Самое лучшее решение работает за 17 ms, но оно с читами (полупрекальк)
0
07.05.2013, 18:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2013, 18:34
Привет! Вот еще темы с ответами:

Необходимо вывести строку prime, если число простое, или composite, если число составное - C++
Уважаемые программисты, проверьте, пожалуйста, решение задачи Проверьте, является ли число простым. Вводится одно число n. Формат...

Функции. Проверить, простое число или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно простым - C++
Помогите пожалуйста 1. Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное число M....

Простое число - C++
Вводиться последовательность из N целых положительных элементов. Определить, содержит ли последовательность хотя бы одно простое число. Для...

Простое число - C++
Простое число Помогите Пожалуйста! Простое число это число которое делится только на 1 и на самого себя. Пользователь...


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

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

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