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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Массив: произвести сдвиг элементов на к позиций, где к-индекс максимального элемента массива http://www.cyberforum.ru/cpp-beginners/thread816209.html
помогите пожалуйста разобраться с указателями, т.к. тема для меня новая и, как оказалось, сложная(( В задаче дан массив A. Нужно заполнить его генератором случайных чисел и затем произвести сдвиг элементов на к позиций, где к-индекс максимального элемента массива. Вот с поиском максимального элемента у меня и не получается(( #include<stdio.h> #include<math.h> #include<conio.h> #include...
C++ Повторяющиеся символы в строке Дано слово. Удалить из него все повторяющиеся буквы, оставив их первые вхождения, то есть в слове должны остаться только различные буквы. Вот как я пытался решить. Но что то не работает. Если вводить вручную по одной букве то все ок. Ошибка в верхнем цикле, но исправить что то не получается. Буду очень признателен если поправите. #include <iostream> using namespace std; int main() 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, из всего что я нашёл по этому, ничего толкового нету кроме того что я понял мол flex и bison работать должны вместе\ если кто-то сталкивался с подобным, подскажите как подключить бизон и флекс к Visual Studio подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 и прочие оптимизации.
 
Текущее время: 06:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru