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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массив: произвести сдвиг элементов на к позиций, где к-индекс максимального элемента массива http://www.cyberforum.ru/cpp-beginners/thread816209.html
помогите пожалуйста разобраться с указателями, т.к. тема для меня новая и, как оказалось, сложная(( В задаче дан массив A. Нужно заполнить его генератором случайных чисел и затем произвести сдвиг...
C++ Повторяющиеся символы в строке Дано слово. Удалить из него все повторяющиеся буквы, оставив их первые вхождения, то есть в слове должны остаться только различные буквы. Вот как я пытался решить. Но что то не работает. Если... http://www.cyberforum.ru/cpp-beginners/thread816201.html
Метод множителей Лагранжа C++
Всем привет. Можете помочь составить программу на методы множителей Лагранжа. Весь интернет обрыл в поисках алгоритмов, но ничего не нашел(
C++ Создать базу данных автомобилей
Помогите написать вот этот пример. Создать базу данных(БД) Автомобилей. БД содержит марка автомобиля, год выпуска, пробег. БД должна загружаться из файла "base.txt" и сохранятся в него. Функции,...
C++ Массив: Заполнить массив из 10 элементов случайным образом в интервале (0..3). http://www.cyberforum.ru/cpp-beginners/thread816174.html
Заполнить массив из 10 элементов случайным образом в интервале (0..3). Например: {1,2,0,3,1,2,3,3,0,1}
C++ Парсер C++ + bison + flex Нужно написать парсер для разбора текста и тегов которыми этот текст обрамлён. Препод предложил изучить flex bison и antlr, из всего что я нашёл по этому, ничего толкового нету кроме того что я... подробнее

Показать сообщение отдельно
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.03.2013, 10:27
Для 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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru