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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
#1

Решето Эратосфена - C++

23.03.2013, 12:26. Просмотров 2070. Ответов 20

Кому надо - программа "Решето Эратосфена" на 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!";
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2013, 12:26     Решето Эратосфена
Посмотрите здесь:

Решето Эратосфена - C++
Возможно ли найти простые числа методом решета Эратосфена с помощью вектора за один проход? Добавлено через 1 минуту У меня...

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

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

Решето Эратосфена - C++
Дано число N (2&lt;=N &lt;=10000), найдите и выведите простые числа между 2 и данным N. Простое число - число, которое может быть разделено...

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
23.03.2013, 12:48     Решето Эратосфена #2
Программа чуть дольше работает, чем то время, что вы указали))
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
23.03.2013, 13:25  [ТС]     Решето Эратосфена #3
Тут, наверное, еще от компьютера зависит. Сколько делает?)
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
23.03.2013, 13:32     Решето Эратосфена #4
скорее не первые 1000000 простых чисел, а простые числа до 1000000
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
23.03.2013, 13:44  [ТС]     Решето Эратосфена #5
Kuzia domovenok, да)

Добавлено через 6 минут
Числа до 1 000 000 000 записывает за 300 секунд. Считает 100 секунд.
Байт
Эксперт C
15639 / 9981 / 1499
Регистрация: 24.12.2010
Сообщений: 18,752
23.03.2013, 14:07     Решето Эратосфена #6
http://ru.wikipedia.org/wiki/%D0%A0%...B8%D0%BD%D0%B0
http://ru.wikipedia.org/wiki/%D0%A0%...B0%D0%BC%D0%B0
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
23.03.2013, 14:11     Решето Эратосфена #7
'\n' вместо endl - и будет счастье...

Добавлено через 28 секунд
Да, и простое число - prime, а не simple.
beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
23.03.2013, 14:27     Решето Эратосфена #8
Умняшечки ))
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
23.03.2013, 15:05  [ТС]     Решето Эратосфена #9
Актуальна

Добавлено через 31 минуту
Актуальна
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
23.03.2013, 17:04     Решето Эратосфена #10
оптимизируйте способ хранения ответа и сделайте быстрый вывод - будет отличная программа...
soon
2538 / 1303 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
23.03.2013, 17:23     Решето Эратосфена #11
http://e-maxx.ru/algo/eratosthenes_sieve
diagon
Higher
1927 / 1193 / 49
Регистрация: 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/%D0%A0%...B0%D0%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)
Т.к. четные числа просеивать не обязательно.
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
23.03.2013, 22:10  [ТС]     Решето Эратосфена #13
Актуальна
MrGluck
Модератор
Эксперт CЭксперт С++
6991 / 4162 / 594
Регистрация: 29.11.2010
Сообщений: 11,044
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 с.
Решето Эратосфена
diagon
Higher
1927 / 1193 / 49
Регистрация: 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 и прочие оптимизации.
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
24.03.2013, 10:39  [ТС]     Решето Эратосфена #16
salam, быстрый вывод??? Он не может быстрее выводится, чем консоль позволяет
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
24.03.2013, 10:46     Решето Эратосфена #17
Цитата Сообщение от diagon Посмотреть сообщение
Для 10^8 писал когда-то такое
Что-то не пойму, что в output.txt...
2 547 1229 1993 2749
diagon
Higher
1927 / 1193 / 49
Регистрация: 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
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
24.03.2013, 10:53     Решето Эратосфена #19
понятно...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2013, 16:56     Решето Эратосфена
Еще ссылки по теме:

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

Решето Эратосфена - C++
Определить простые числа методом просеивания с помощью &lt;&lt;решета Эратосфена&gt;&gt; с _битовой упаковкой_ данных при сохранении. #include...

Решето Эратосфена с графикой - C++
Нужно сделать решето эратосфена, с введением чисел от 2 до N, и чтобы выводил все числа и вычеркивал, не знаю как это реализовать, знания...

Простые числа. Решето Эратосфена - C++
Здравствуйте! Нужна ваша помощь, не могу понять условие этой задачи: Даны натуральное число n, целые числа a1,.....,an. Рассмотреть...

Решето Эратосфена. Как ускорить? - C++
Этот код не проходит задачу. доля секунды. как ускорить. или каким методом проидет #include &lt;bits/stdc++.h&gt; using namespace std; ...


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

Или воспользуйтесь поиском по форуму:
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
24.03.2013, 16:56  [ТС]     Решето Эратосфена #20
Актуальна

Добавлено через 3 часа 18 минут
Актуальна
Yandex
Объявления
24.03.2013, 16:56     Решето Эратосфена
Ответ Создать тему
Опции темы

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