Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 17:28     итое простое число #1
Нужно найти N-ое простое число. (1 <= N <= 10^7).
Вопрос состоит в том, как эту задачу можно решать. Только блочным решетом, асимптотика O(n log ( log (n))) ??
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

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

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

C++ Передать в функцию целое число. Функция заменяет его на ближайшее простое число, которое больше или меньше исходного. Вернуться в main( ) и распечатат
C++ Дано натуральное число. Найти ближайшее простое число
C++ Задача: Найти, входит ли в последовательность I(итое)число Фибоначчи
Дано простое число. Составить функцию,которая будет находить следующее за ним простое число. C++
Функции. Проверить, простое число или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно простым C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.05.2013, 19:02     итое простое число #2
Цитата Сообщение от Ternsip Посмотреть сообщение
По памяти должно влезть ??
Разумеется, там же потребуется хранить простые числа до корня (а их можно хранить очень компактно, тратя один байт на каждое простое число) + константа на блок.

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

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

Добавлено через 4 минуты
еще позволю себе отметить, что в блочном решете важна степень прекалка. при большом предпосчете блочное решето, действительно, очень быстрое...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 можно добиться линейной сложности у решета Эратосфена.
Но, несмотря на проигрыш в ассимптотике, блочное решето Эратосфена гораздо более эффективно использует кеш и, следовательно, имеет сильно меньшую константу.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.05.2013, 20:31     итое простое число #6
разговор, помнится, был об асимптотике, потому собственно говоря... линейное решето не стал упоминать по понятным всем причинам. на счет эффективности блочного решета никто не спорил вроде...
Ternsip
 Аватар для 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;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.05.2013, 18:28     итое простое число #8
будьте любезны ссылочку на задачу и время вашего сабмита.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2013, 18:34     итое простое число
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Ternsip
 Аватар для 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, но оно с читами (полупрекальк)
Yandex
Объявления
07.05.2013, 18:34     итое простое число
Ответ Создать тему

Метки
prime
Опции темы

Текущее время: 00:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru