Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
1

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

24.04.2013, 11:20. Просмотров 4221. Ответов 16

Доброго времени суток.
Мне нужно получить список первых 1.000.000.0 простых чисел. (10^7 первых)
Нужен дамб этих чисел в текстовом файле (через пробел).
Для того, чтобы сделать читерский прекалк и вшить их в устройство.
Я пытался найти в гугле такой большой список, но тщетно.
Может кто-то умеет быстро их посчитать и записать в файл ? Или уже имеется этот список ?
Обещаю много лайков.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.04.2013, 11:20
Ответы с готовыми решениями:

Найти все двухзначные простые числа, определив функцию для вычисления простых чисел
Найти все двухзначные простые числа, определив функцию для вычисления простых чисел на C++

Удалить все простые числа и найти среднее арифметическое до и после удаления простых чисел
Помогите пожалуйста разобрать ошибки и дописать программу. Ошибки: Функции должны возвращать...

Создать односвязный список из последовательности чисел, удалить из него все простые числа
Прошу помощи, не могу понять в чем ошибка, надо создать односвязный список из последовательности...

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

16
Helter Skelter
64 / 64 / 19
Регистрация: 19.09.2012
Сообщений: 133
24.04.2013, 11:36 2
http://www.naturalnumbers.org/primes.html
1
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 12:58  [ТС] 3
hofmn, большое спасибо, мне понравилась та программа, но я не знаю за какую асимптотику она находит простое число и вызывает у меня недоверие + она не самым удобным способом сохраняет найденные числа, а если точнее, то разбивает список на несколько файлов, в которых ещё ставит какие-то лишние числа и запятые

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

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

Добавлено через 5 минут
Кароче, если кто-то может через тест Миллера-Рабина дать брутфорс, то хелп!!
0
397 / 353 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 13:40 8
Цитата Сообщение от Ternsip Посмотреть сообщение
Сначала подумал, что тест Миллера-Рабина пригодится. Но, либо криво реализовал, либо это не сильно помогает.
вообщето тест Миллера-Рабина должен помочь, может у тебя происходит переполнение?
0
667 / 195 / 29
Регистрация: 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 первых простых чисел
0
667 / 195 / 29
Регистрация: 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;
}
0
Higher
1944 / 1210 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2013, 22:36 11
Цитата Сообщение от Ternsip Посмотреть сообщение
теперь всё ок
Все, кроме скорости.
Сложность - O(n * logn) и там еще константа неслабая. Единственный плюс - константа по памяти.

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

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

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

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

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

Добавлено через 1 минуту
diagon, там либо тест Миллера-Рабина, либо Агравала — Каяла — Саксены
0
Higher
1944 / 1210 / 120
Регистрация: 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/ это решетом делают ?
Для чисел мерсенна вообще свои алгоритмы. Как минимум, там нужно перебирать не весь диапазон, а просто степени двойки.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.04.2013, 23:17

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Поиск простых чисел в диапазоне 1000-2000, две любые части которых - также простые
Информатика, 1 курс, прошу помочь с программой Написать функцию проверки, является ли заданное...

Линейный список. Удаление простых чисел из него
Построить линейный список из входной последовательности чисел. Удалить из него все простые числа ...

Вывести список простых чисел до введенного с клавиатуры значения
Ребят помогите плз!В с++ ваще невтыкаю, еще в паскале шарю кое как а тут нифига(Вообщем оч простая...

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа....


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

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

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