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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Динамические структуры данных. Составить программу, которая содержит текущую информацию о книгах в библиотеке http://www.cyberforum.ru/cpp-beginners/thread847093.html
не могу решить Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: • номер УДК; • фамилию и инициалы автора; • название; • год издания;...
C++ Функции библиотеки для работы со строками и символами С помощью текстового редактора создать файл, содержащий текст, длина которого не превышает 700 символов (длина строки текста не должна превышать 70 символов). Имя файла должно иметь расширение... http://www.cyberforum.ru/cpp-beginners/thread847091.html
C++ Функции библиотеки для работы со строками и символами
Помогите с решением С помощью текстового редактора создать файл, содержащий текст, длина которого пе превышает 1000 символов (длина строки текста не должна превышать 70 символов). Имя файла...
Структуры: хранение данных о планшетных сканерах C++
Помогите, не могу решить Для хранения данных о планшетных сканерах описать структуру вида: struct scan_info{ char model; // наименование модели int price: // цена double x_s1ze: //...
C++ Не пойму тайный смысл фразы Страуструпа http://www.cyberforum.ru/cpp-beginners/thread847064.html
Читаю Страуструпа про компоновку и нашел там такое предложение: Причина, по которой в заголовочные файлы рекомендуется включать определения простых констант, а определения агрегатов включать не...
C++ Дан текстовый файл. Переписать компоненты файла в другой файл, заменив при этом каждое сочетание букв “no” на “on” Дан текстовый файл. Переписать компоненты файла в другой файл, заменив при этом каждое сочетание букв “no” на “on”. :( Помогите, пожалуйста!! подробнее

Показать сообщение отдельно
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
24.04.2013, 16:24  [ТС]
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru