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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

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

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

Доброго времени суток.
Мне нужно получить список первых 1.000.000.0 простых чисел. (10^7 первых)
Нужен дамб этих чисел в текстовом файле (через пробел).
Для того, чтобы сделать читерский прекалк и вшить их в устройство.
Я пытался найти в гугле такой большой список, но тщетно.
Может кто-то умеет быстро их посчитать и записать в файл ? Или уже имеется этот список ?
Обещаю много лайков.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2013, 11:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Простые числа. Список простых чисел (C++):

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

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

Линейный список. Удаление простых чисел из него - C++
Построить линейный список из входной последовательности чисел. Удалить из него все простые числа #include <iostream> #include...

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

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

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б - C++
#include <stdio.h> #include <iostream> #include <conio.h> #include <math.h> using std::cout; using std::cin; using...

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

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

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

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

Используйте решето Эратосфена, это самой простой алгоритм поиска простых чисел. К тому же оно очень мощно оптимизируется, но это уже совсем другая история.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 22:53  [ТС] #12
diagon, на решето памяти не хватает, увы, это я в общем. В задачах, где требуется этот тест, обычно ограничение по памяти.
0
diagon
Higher
1929 / 1195 / 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 вместо обычного массива.
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 23:01  [ТС] #14
diagon, например если требуется сгенерить быстро все простые числа в диапазоне 10^17-10^20

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

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

Добавлено через 1 минуту
Цитата Сообщение от Ternsip Посмотреть сообщение
10^20
Забудьте :)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2013, 23:06
Привет! Вот еще темы с ответами:

Мин/макс. из n чисел; простые числа - C++
Написать программу нахождения минимального и максимального из n (n&gt;0) введенных чисел. Вывести все простые числа в интервале от 1 до N....

Нахождение простых чисел до заданого числа n - C++
помогите с программой для находжения простых чисел до заданого числа n. просьба зделать это без массивов.

Подсчитать сумму простых чисел до числа N в сетях Петри - C++
выдали задание &quot;подсчитать сумму простых чисел до числа N&quot; сама программа лёгкая, но проблема в том, что нужно это всё сделать в сетях...

Вывести 5 простых чисел, которые больше введенного числа - C++
вывести 5 простых чисел, которые больше введенного числа; С++ помогите решить с помощью только циклов,находил на форуме с помощью...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
29.04.2013, 23:06
Ответ Создать тему
Опции темы

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