CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
1

Решето Эратосфена

23.03.2013, 12:26. Показов 28815. Ответов 21

Кому надо - программа "Решето Эратосфена" на C++. Записывает в файл 1 000 000 первых простых чисел за 1/10 секунды (без вывода)!!!

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
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
int main() {
    const int N = 1000000;
    vector<bool>simple(N, true);
    ofstream f("simple.txt");
    for(int i = 2; i * i <= N; ++i) {
        if(simple[i] == true) {
            for(int j = i * i; j < N; j += i) {
                //cout << j << " ";
                simple[j] = false;
            }
        }
    }
 
    for(int i = 2; i < N; ++i) {
        if(simple[i] == true) {
            f << i << endl;
        }
    }
 
 
 
    cout << "Completed!";
}
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.03.2013, 12:26
Ответы с готовыми решениями:

Решето Эратосфена
Подскажите реализацию (код) метода шифрования - решета Эратосфена, пожалуйста.

Решето Эратосфена
Здравствуйте. Реализовал алгоритм &quot;Решето Эратосфена&quot; в виде класса. Взгляните, пожалуйста, и...

Решето Эратосфена
Возможно ли найти простые числа методом решета Эратосфена с помощью вектора за один проход? ...

Решето Эратосфена
В решете эратосфена из книги в условии есть непонятная вещь: if (i * 1ll * i &lt;= n) - возле единицы...

21
4 / 4 / 1
Регистрация: 07.01.2013
Сообщений: 103
23.03.2013, 12:48 2
Программа чуть дольше работает, чем то время, что вы указали))
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
23.03.2013, 13:25  [ТС] 3
Тут, наверное, еще от компьютера зависит. Сколько делает?)
0
3753 / 3073 / 850
Регистрация: 25.03.2012
Сообщений: 11,375
Записей в блоге: 1
23.03.2013, 13:32 4
скорее не первые 1000000 простых чисел, а простые числа до 1000000
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
23.03.2013, 13:44  [ТС] 5
Kuzia domovenok, да)

Добавлено через 6 минут
Числа до 1 000 000 000 записывает за 300 секунд. Считает 100 секунд.
0
Диссидент
Эксперт C
26949 / 16830 / 3698
Регистрация: 24.12.2010
Сообщений: 37,768
23.03.2013, 14:07 6
http://ru.wikipedia.org/wiki/%... 0%BD%D0%B0
http://ru.wikipedia.org/wiki/%... 0%BC%D0%B0
0
2831 / 1640 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
23.03.2013, 14:11 7
'\n' вместо endl - и будет счастье...

Добавлено через 28 секунд
Да, и простое число - prime, а не simple.
0
4 / 4 / 1
Регистрация: 07.01.2013
Сообщений: 103
23.03.2013, 14:27 8
Умняшечки ))
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
23.03.2013, 15:05  [ТС] 9
Актуальна

Добавлено через 31 минуту
Актуальна
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
23.03.2013, 17:04 10
оптимизируйте способ хранения ответа и сделайте быстрый вывод - будет отличная программа...
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
23.03.2013, 17:23 11
http://e-maxx.ru/algo/eratosthenes_sieve
1
Higher
1952 / 1218 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.03.2013, 20:07 12
Цитата Сообщение от Байт Посмотреть сообщение
http://ru.wikipedia.org/wiki/%D0%A0%...B8%D0%BD%D0%B0
http://ru.wikipedia.org/wiki/%... 0%BC%D0%B0
Решето Сундарама уступает даже лобовому перебору делителей.
Решето Аткина будет побыстрее кода из поста ТС, но ощутимо медленнее оптимизированного решета Эратосфена.

C++
1
j += i
Можно без проблем заменить на
C++
1
j += 2 * i;
И циклы вида
C++
1
for(int i = 2; i < N; ++i)
на
C++
1
for (int i = 3; i < N; i +=2)
Т.к. четные числа просеивать не обязательно.
1
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
23.03.2013, 22:10  [ТС] 13
Актуальна
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
24.03.2013, 04:48 14
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
int main()
{
    const int N = 100000000;
    vector<bool> simple(N, true);
    ofstream f("simple.txt");
    for(int i = 2; i * i <= N; ++i)
        if(simple[i])
            for(int j = i * i; j < N; j += 2 * i)
                simple[j] = false;
 
    for (int i = 3; i < N; i += 2)
        if(simple[i])
            f << i << '\n';
 
    cout << "Completed!";
}
выполнило за 4.467 с.
Решето Эратосфена
0
Higher
1952 / 1218 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.03.2013, 10:27 15
Для 10^8 писал когда-то такое
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <math.h>
 
#define true 1
#define false 0
 
#pragma region bitvector
 
#include <string.h>
#include <limits.h>
#include <stdlib.h>
 
#define BYTES sizeof(size_t)
#define BITS (BYTES * 8)
#define BITVECTOR_SIZE(n) ( n / BITS + (n % BITS != 0) )
 
#define BITVECTOR_INIT(vector_name, n)  \
    size_t * vector_name = (size_t*) malloc(BITVECTOR_SIZE(n) * BYTES); 
 
#define BITVECTOR_CLEAR(vector_name, n) \
    memset(vector_name, 0, BITVECTOR_SIZE(n) * BYTES);
 
#define ARR_INDEX(index) (index / (sizeof(size_t) * 8) )
#define BIT_INDEX(index) (index % (sizeof(size_t) * 8) )
 
#define BIT_TEST(vector, index) \
    ( vector[ARR_INDEX(index)] & (1 << BIT_INDEX(index)) )
 
#define SIZE_T_MAX ( ~( (size_t) 0) )
 
 
#define BIT_SET_TRUE(vector, index) \
    vector[ARR_INDEX(index)] |= 1 << (size_t) BIT_INDEX(index);
 
#define BIT_SET(vector, index, value)                       \
    if (value) vector[ARR_INDEX(index)] |= 1 << (size_t) BIT_INDEX(index);          \
    else vector[ARR_INDEX(index)] &= SIZE_T_MAX ^ (1 << (size_t) BIT_INDEX(index));
 
#define BIT_XOR(vector, index)  \
    vector[ARR_INDEX(index)] ^= 1 << BIT_INDEX(index);
 
#define BITVECTOR_FREE(vector) \
    free(vector);
 
#pragma endregion
 
FILE *output;
 
int sieve_first_block(unsigned int *primes, int n)
{
    primes[0] = 2;
    int counter = 1;
 
    int sq = (int) (sqrt(1.0 * n) + 1e-7);
 
    n = (n - 1) / 2;
 
    BITVECTOR_INIT(sieve, n)
        BITVECTOR_CLEAR(sieve, n)
 
        for (int i = 3; i <= sq; i += 2)
        {
            if (!BIT_TEST(sieve, i / 2))
            {
                primes[counter++] = i;
 
                for (int j = i * i / 2; j <= n; j += i)
                {
                    BIT_SET_TRUE(sieve, j)
                }
            }
        }
 
        for (int i = (sq + 1 + (sq % 2 != 0)) / 2; i <= n; ++i)
        {
            if (!BIT_TEST(sieve, i))
                primes[counter++] = 2 * i + 1;
        }
 
        BITVECTOR_FREE(sieve)
 
            return counter;
}
 
void segmented_sieve(int n)
{
    int block_size = 250000;
 
    int primes_size = 1229;
 
    unsigned int primes[100500];
 
    int real_primes_size = sieve_first_block(primes, block_size);
 
    for (int i = 0; i < real_primes_size; i += 100)
    {
        fprintf(output, "%d ", primes[i]);
    }
 
    int counter = real_primes_size % 100;
 
    block_size = (block_size) / 2;
 
    BITVECTOR_INIT(sieve, block_size)
 
        fflush(output);
 
    for (int block_begin = block_size; block_begin + block_size <= n / 2; block_begin += block_size)
    {
        int block_end = block_begin + block_size;
 
        BITVECTOR_CLEAR(sieve, block_size)
 
            for (int i = 1; i < primes_size; ++i)
            {
                int current_prime = primes[i];
 
                int start_index = block_begin * 2 / current_prime * current_prime + current_prime * (block_begin * 2 % current_prime != 0);
 
                if (start_index % 2 == 0)
                    start_index += current_prime;
 
                start_index /= 2;
 
                start_index -= block_begin;
 
                for (int j = start_index; j < block_size; j += current_prime)
                {
                    BIT_SET_TRUE(sieve, j)
                }
            }
 
            for (int i = 0; i < block_size; ++i)
            {
                if (!BIT_TEST(sieve, i))
                {
                    if (++counter % 100 == 1)
                    {
                        fprintf(output, "%d ", 2 * (i + block_begin) + 1);
                    }
                }
            }
    }
 
    BITVECTOR_FREE(sieve)
}
 
int main()
{
    output = stdout;
    //output = fopen("output.txt", "w");
 
    segmented_sieve(100 * 1000 * 1000);
 
    return 0;
}
Надо будет как-нибудь допилить сюда wheel factorization по 30 или даже по 210 и прочие оптимизации.
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
24.03.2013, 10:39  [ТС] 16
salam, быстрый вывод??? Он не может быстрее выводится, чем консоль позволяет
0
2831 / 1640 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
24.03.2013, 10:46 17
Цитата Сообщение от diagon Посмотреть сообщение
Для 10^8 писал когда-то такое
Что-то не пойму, что в output.txt...
2 547 1229 1993 2749
0
Higher
1952 / 1218 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.03.2013, 10:49 18
Цитата Сообщение от Somebody Посмотреть сообщение
Что-то не пойму, что в output.txt...
Там выводится каждое число, номер которого % 100 == 1
Писалось под эту задачу - http://www.spoj.com/problems/TDPRIMES/
То есть надо закомментить 137 строку и в 95 строке заменить i += 100 на ++i
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
24.03.2013, 10:53 19
понятно...
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
24.03.2013, 16:56  [ТС] 20
Актуальна

Добавлено через 3 часа 18 минут
Актуальна
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.03.2013, 16:56
Помогаю со студенческими работами здесь

Решето Эратосфена
Простое число — это любое целое число, которое точно делится без остатка только само на себя и на...

Решето Эратосфена
Как можно реализовать? Подскажите плиз

Решето Эратосфена
Написать функция для выполнения алгоритма решить Эратосфена! зарания спасибо!!!

Решето Эратосфена
В общем задание посчитать количество простых чисел до заданного числа N. Написал такой алгоритм,...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru