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

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

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

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

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

Нужно найти 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     итое простое число
Посмотрите здесь:

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

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

простое число - C++
Проверить,является ли введённое целое положительное число простым. простым называется число, которое имеет только два делителя(еденицу и...

простое число - C++
Подскажите пожалуйста как проверить является ли число простым?

Простое число - C++
bool prostoechislo(int n) //функция определяющая простое число или нет { if (n &lt; 2) return false; if (n == 2) return true; ...

простое число - C++
Составить программу определяющую яв-ся ли число простым?

Простое число и массивы - C++
есть задача: Дан массив n целых чисел. Если в массиве есть хотя бы одно простое число, то создается новый массив, в котором все члены...

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

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

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

Добавлено через 4 минуты
еще позволю себе отметить, что в блочном решете важна степень прекалка. при большом предпосчете блочное решето, действительно, очень быстрое...
diagon
Higher
1928 / 1194 / 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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
02.05.2013, 20:31     итое простое число #6
разговор, помнится, был об асимптотике, потому собственно говоря... линейное решето не стал упоминать по понятным всем причинам. на счет эффективности блочного решета никто не спорил вроде...
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.05.2013, 18:28     итое простое число #8
будьте любезны ссылочку на задачу и время вашего сабмита.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2013, 18:34     итое простое число
Еще ссылки по теме:

Простое число(проверьте пожалуйста) - C++
Надо определить является ли введенное число простым или состовным. из алгебры известно что если она не делится ни на одно число до корня...

Вывести N-ое по счету простое число - C++
Вводится целое число N, 0 &lt; N &lt; 105. Вывести N-ое по счету простое число. Пример ввода: 1 Пример вывода: 2 Пример ввода: 5 ...

Найти простое число в массиве - C++
Как в С++ в массиве найти ПРОСТОЕ число (которое делится только на себя и на единицу) ? Буду очень благодарен

Объясните проверку на простое число - C++
Подскажите пожалуйста, сам я из леса и разобраться не получается, есть программа проверяющая число на простоту. Читаю книгу &quot;С++ без...

Простое число или нет - C++
#include &lt;iostream&gt; #include&quot;conio.h&quot; #include&quot;math.h&quot; using namespace std; int main() { int n,i,k; bool np; ...


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

Или воспользуйтесь поиском по форуму:
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     итое простое число
Ответ Создать тему
Опции темы

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