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

Простые числа. Список простых чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 11:20     Простые числа. Список простых чисел #1
Доброго времени суток.
Мне нужно получить список первых 1.000.000.0 простых чисел. (10^7 первых)
Нужен дамб этих чисел в текстовом файле (через пробел).
Для того, чтобы сделать читерский прекалк и вшить их в устройство.
Я пытался найти в гугле такой большой список, но тщетно.
Может кто-то умеет быстро их посчитать и записать в файл ? Или уже имеется этот список ?
Обещаю много лайков.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hofmn
Helter Skelter
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
24.04.2013, 11:36     Простые числа. Список простых чисел #2
http://www.naturalnumbers.org/primes.html
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 12:58  [ТС]     Простые числа. Список простых чисел #3
hofmn, большое спасибо, мне понравилась та программа, но я не знаю за какую асимптотику она находит простое число и вызывает у меня недоверие + она не самым удобным способом сохраняет найденные числа, а если точнее, то разбивает список на несколько файлов, в которых ещё ставит какие-то лишние числа и запятые

Добавлено через 28 минут
Жду ещё ответов. Пока пишу сам прогу для генерации, но она долго делает прекалк на моём компе

Добавлено через 48 минут
народ выручайте, задача вполне преподъёмная
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 13:02     Простые числа. Список простых чисел #4
Цитата Сообщение от Ternsip Посмотреть сообщение
Мне нужно получить список первых 1.000.000.0 простых чисел. (10^7 первых)
Нужен дамб этих чисел в текстовом файле (через пробел).
Для того, чтобы сделать читерский прекалк и вшить их в устройство.
а зачем если не секрет?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 13:18  [ТС]     Простые числа. Список простых чисел #5
aram_gyumri, ну мне нужно быстро отвечать на запросы типа "Номер простого числа (x) "
prime_num(7) = 4. Всё остальное секрет )) Если честно, то сначала, я наткнулся на задачу, в которой нужно это делать, но без предрассчёта с ограничением в 2 секунды и сильным ограничением по памяти. Я узнал зачем нужна эта задача и теперь мне очень хочется очень сильно ускорить эту функцию до O(1), а затем ещё ускорить на аппаратном уровне.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 13:20     Простые числа. Список простых чисел #6
Ternsip, а вам точно нужно найти 10^7 простых чисел? или все простые до 10^7?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 13:31  [ТС]     Простые числа. Список простых чисел #7
aram_gyumri, Я, вроде, написал, что 10^7 простых (10^7 первых простых). Сначала подумал, что тест Миллера-Рабина пригодится. Но, либо криво реализовал, либо это не сильно помогает.

Добавлено через 5 минут
Кароче, если кто-то может через тест Миллера-Рабина дать брутфорс, то хелп!!
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 13:40     Простые числа. Список простых чисел #8
Цитата Сообщение от Ternsip Посмотреть сообщение
Сначала подумал, что тест Миллера-Рабина пригодится. Но, либо криво реализовал, либо это не сильно помогает.
вообщето тест Миллера-Рабина должен помочь, может у тебя происходит переполнение?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 16:24  [ТС]     Простые числа. Список простых чисел #9
aram_gyumri, Вот, взял код у Иванова Максима, который e-maxx сделал.
Кликните здесь для просмотра всего текста
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include "windows.h"
 
using namespace std;
 
template <class T, class T2>
T gcd (const T & a, const T2 & b){
    return (a == 0) ? b : gcd (b % a, a);
}
 
template <class T>
bool even (const T & n){
    return (n & 1) == 0;
}
 
template <class T>
void bisect (T & n){
    n >>= 1;
}
 
template <class T>
void redouble (T & n){
    n <<= 1;
}
 
 
template <class T>
void mulmod (T & a, T b, const T & n){
    a *= b;
    a %= n;
}
 
template <>
void mulmod (int & a, int b, const int & n){
    a = int( (((long long)a) * b) % n );
}
 
template <>
void mulmod (unsigned & a, unsigned b, const unsigned & n){
    a = unsigned( (((unsigned long long)a) * b) % n );
}
 
template <>
void mulmod (unsigned long long & a, unsigned long long b, const unsigned long long & n){
    if (a >= n)
        a %= n;
    if (b >= n)
        b %= n;
    unsigned long long res = 0;
    while (b)
        if (!even (b)){
            res += a;
            while (res >= n)
                res -= n;
            --b;
        }
        else{
            redouble (a);
            while (a >= n)
                a -= n;
            bisect (b);
        }
    a = res;
}
 
template <class T>
void transform_num (T n, T & p, T & q){
    T p_res = 0;
    while (even (n)){
        ++p_res;
        bisect (n);
    }
    p = p_res;
    q = n;
}
 
template <class T, class T2>
T powmod (T a, T2 k, const T & n){
    T res = 1;
    while (k)
        if (!even (k)){
            mulmod (res, a, n);
            --k;
        }
        else{
            mulmod (a, a, n);
            bisect (k);
        }
    return res;
}
 
template <class T, class T2>
bool miller_rabin (T n, T2 b) {
    if (n == 2)
        return true;
    if (n < 2 || even (n))
        return false;
    if (b < 2)
        b = 2;
    for (T g; (g = gcd (n, b)) != 1; ++b)
        if (n > g)
            return false;
    T n_1 = n;
    --n_1;
    T p, q;
    transform_num (n_1, p, q);
    T rem = powmod (T(b), q, n);
    if (rem == 1 || rem == n_1)
        return true;
    for (T i=1; i<p; i++){
        mulmod (rem, rem, n);
        if (rem == n_1)
            return true;
    }
    return false;
}
 
int main(){     
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int cnt;
    cin >> cnt;
    unsigned long long k = 2;
    while (cnt > 0) {
        if (miller_rabin(k, 19)) {
            printf("%I64d ", k);
            cnt--;
        }
        k++;
    }
    return 0;
}


на http://codeforces.com/problemset/customtest на ввходе 10^5 уже 4.5 секунды пашет, когда обычный пробег до корня числа пашет 1.5 секунды

Добавлено через 47 минут
Переписал почище
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
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include "windows.h"
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witness(long long a, long long n){
    long long d = 1;
    long long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < (1 << i)) continue;
        long long x = d;
        d = (long long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long long(d) * a) % n;
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries){
    forn(it, tries){
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
int main(){     
    int cnt;
    cin >> cnt;
    unsigned long long k = 2;
    while (cnt > 0) {
        if (MillerRabin(k, 19)) {
            printf("%I64d ", k);
            cnt--;
        }
        k++;
    }
    return 0;
}
Но всёравно отрабатывает для 10^5 в 2 раза дольше чем если бы до sqrt(n) шёл каждый раз

Добавлено через 6 минут
тратим 1197 итераций на каждую проверку числа. увы

Добавлено через 50 минут
Всё пробрутил через MillerRabin сейчас залью текстовичёк

Добавлено через 4 минуты
кстати, возможно я ошибся для чисел больших int т.к. << - 32 разрядное смещение. А так всё верно.

Добавлено через 48 минут
http://rghost.ru/45519770 тут архиф с текстовым файлом, который содержит 10000000 первых простых чисел
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 22:14  [ТС]     Простые числа. Список простых чисел #10
Немного улучшил тест Миллера, т.к. в нём было переполнение 64 - битного типа. теперь всё ок
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
long long mulmod(long long a, long long b, long long MOD){
    if (b == 0) return 0;
    long long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long long a, long long n){
    long long d = 1;
    long long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries){
    for(int it = 0; it < tries; it++){
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2013, 22:36     Простые числа. Список простых чисел #11
Цитата Сообщение от Ternsip Посмотреть сообщение
теперь всё ок
Все, кроме скорости.
Сложность - O(n * logn) и там еще константа неслабая. Единственный плюс - константа по памяти.

Используйте решето Эратосфена, это самой простой алгоритм поиска простых чисел. К тому же оно очень мощно оптимизируется, но это уже совсем другая история.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 22:53  [ТС]     Простые числа. Список простых чисел #12
diagon, на решето памяти не хватает, увы, это я в общем. В задачах, где требуется этот тест, обычно ограничение по памяти.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2013, 22:58     Простые числа. Список простых чисел #13
Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, на решето памяти не хватает, увы
При правильной реализации оно использует http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\sqrt{n}}{\log\sqrt{n}} памяти (список простых чисел до корня).
Но даже если не писать блочное решето, а обойтись обычным, то памяти должно хватить. Ну, в крайнем случае нужно будет использовать bitset вместо обычного массива.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 23:01  [ТС]     Простые числа. Список простых чисел #14
diagon, например если требуется сгенерить быстро все простые числа в диапазоне 10^17-10^20

Добавлено через 2 минуты
diagon, 4 ГБ памяти
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2013, 23:06     Простые числа. Список простых чисел #15
Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, например если требуется сгенерить быстро все простые числа в диапазоне 10^17-10^19
Особо быстро их в любом случае не сгенерить :) Слишком большой диапазон для поиска. Там примерно 1017 простых чисел :)

Вроде бы блочное решето Аткина должно справится с вашими запросами (но даже оно работать будет ну ооочень долго).

Добавлено через 1 минуту
Цитата Сообщение от Ternsip Посмотреть сообщение
10^20
Забудьте :)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 23:11  [ТС]     Простые числа. Список простых чисел #16
diagon, А как вы думаете, сколько оно будет работать ?

Добавлено через 1 минуту
diagon, http://habrahabr.ru/post/168417/ это решетом делают ?

Добавлено через 1 минуту
diagon, там либо тест Миллера-Рабина, либо Агравала — Каяла — Саксены
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2013, 23:17     Простые числа. Список простых чисел
Еще ссылки по теме:

Подсчитать количество простых чисел в последовательности, больших заданного числа М C++
C++ Удалить все простые числа и найти среднее арифметическое до и после удаления простых чисел
Подсчитать сумму простых чисел до числа N в сетях Петри C++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2013, 23:17     Простые числа. Список простых чисел #17
Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, А как вы думаете, сколько оно будет работать ?
За несколько лет должно справиться.
Ну, там сложно оценивать. Но, допустим, нам нужно совершить n инкрементов (у решета эратосфена константа меньше, чем у инкрементов, у аткина повыше будет).
Инкременты до 10^9 выполняются примерно секунду. Значит, чтобы найти простые числа до 10^20 потребуется 10^11 секунд, это примерно 3000 лет. Ну, подсчеты очень грубые, так что погрешность плюс минус 1-2 тысячи лет.

Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, 4 ГБ памяти
А по моим подсчетам 1.5 ГБ (для 10^20)

Добавлено через 1 минуту
Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, http://habrahabr.ru/post/168417/ это решетом делают ?
Для чисел мерсенна вообще свои алгоритмы. Как минимум, там нужно перебирать не весь диапазон, а просто степени двойки.
Yandex
Объявления
29.04.2013, 23:17     Простые числа. Список простых чисел
Ответ Создать тему

Метки
precalc, prime numbers
Опции темы

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