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

@1234569 · Регистрация: 25.11.2010

Студворк — интернет-сервис помощи студентам

Определить простые числа методом просеивания с помощью <<решета Эратосфена>> с _битовой упаковкой_ данных при сохранении.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <math.h>
#include <fstream.h>
#define MAXN 100000000
char sieveE[MAXN];
 
void main()
{ 
    ofstream f1("out.txt"); 
                //xxx: Папа рус, мама рус, почему же я индус?
    f1 << "2\n"; 
                //yyy: И уже который год я пишу индусский код.
    unsigned long j,i,n=MAXN,sqrtLimit=(unsigned long)sqrt(n);
        sieveE[1]=1;
 
        for(i=3;i<=sqrtLimit;i+=2)
            if(!sieveE[i]) 
                for(j=i*i;j<=n;j+=i<<1)
                    sieveE[j] = 1;               
        for(i=3; i<=n ; i+=2)
            if(!sieveE[i]) f1 << i << endl;
}

1)Что в данном контексте значит "битовая упаковка" и как она реализуется?
2)Возможно ли вывести 2 внутри цикла?
3)Возможно ли задать нижний предел?
4)Возможно ли убрать #define MAXN и char sieveE[MAXN] в main?
5)Как я понимаю, if(!sieveE[i]) проверяет sieveE[i] на ложность, но от чего?

@1234569 · 17.12.2010, 00:29 **[ТС]**

Добавил вывод в файл и вывод из файла:

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
#include <math.h>//нужен для sqrt(n)
#include <fstream.h>//нужен для ifstream, ofstream, cin, cout
#include <windows.h>//нужен для вывода кириллицы
#include <vector>//нужен для вектора
 
using std::vector;
unsigned long MAXN;
vector<char> sieveE(100);
 
void main()
{ 
    system("chcp 1251>nul");//меняем кодировку консоли
    cout<<"Решето Эратосфена\n"<<"Введите верхний предел: ";//потребление памяти для вычисления 100 000 000 простых чисел - 100МБайт. Для 1 000 000 000 - 1.5ГБ
    cin>>MAXN;
    unsigned long j,i,n=MAXN,sqrtLimit=(unsigned long)sqrt(n);
    sieveE.resize(MAXN*sizeof(char));//изменяем размер массива
    sieveE[1]=1;
    ofstream f1("out.txt");//открываем поток файла на запись
                //xxx: Папа рус, мама рус, почему же я индус?
    f1<<"2\n"; 
                //yyy: И уже который год я пишу индусский код.
        for(i=3;i<=sqrtLimit;i+=2)
            if(!sieveE[i]) 
                for(j=i*i;j<=n;j+=i<<1)
                    sieveE[j]=1;               
        for(i=3;i<=n;i+=2)
            if(!sieveE[i]) f1<<i<<"\n";//выводим в файл
        f1.close();//закрываем поток файла
 
    char be;
        cout<<"Начать вывод(Y)?"<<endl;
            cin>>be;
        if(be=='y'||be=='Y')//начало вывода на экран
            {
    char a;
                    ifstream f1("out.txt");//открываем поток файла на чтение
                    if(!f1)
                        {
                            cout<<"Программа выполнила недопустимую операцию, и будет."<<endl;//обработка отсутствия файла
                        }
                    while(!f1.eof())//выводим до конца файла
                        {
                            f1.get(a);
                            cout<<a;
                        }
                    f1.close();//закрываем поток файла
            }
        else cout<<"Вывод отменён\n";
        cout << "Нажмите любую клавишу для выхода"<<endl;
        cin>>be;
 
}

По прежнему остаётся 3 вопроса:
1)Что значит "битовая упаковка" и как она реализуется?
2)Возможно ли вывести 2 внутри цикла?
3)Возможно ли задать нижний предел?

@1234569 · 18.12.2010, 21:54 **[ТС]**

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
//Era3, потребление памяти для вычисления 100 000 000 простых чисел - 100МБ. Для 1 000 000 000 - 1.5ГБ
#include <math.h>//нужен для sqrt(n)
#include <fstream.h>//нужен для ifstream, ofstream, cin, cout
#include <windows.h>//нужен для вывода кириллицы
 
char *sieveE;
 
void main()
{ 
    system("chcp 1251>nul");//меняем кодировку консоли
    unsigned long j,i,n;
 
    ofstream f1("out.txt");//открываем поток файла на запись
    cout<<"Решето Эратосфена\n"<<"Введите верхний предел: ";
        cin>>n;
        if(n<2){cout<<"Мало"<<endl;return;}
 
    sieveE=new char[n+1];//изменяем размер массива
    sieveE[1]=1;
 
    for(i=2;i<n;i++) sieveE[i]=0;
    
    unsigned long sqrtLimit=(unsigned long)sqrt((float)n);
                //xxx: Папа рус, мама рус, почему же я индус?
    f1<<"2\n";  //yyy: И уже который год я пишу индусский код.           
        for(i=3;i<=sqrtLimit;i+=2)
            if(!sieveE[i]) 
                for(j=i*i;j<=n;j+=i<<1)
                    sieveE[j]=1;               
        for(i=3;i<=n;i+=2)
            if(!sieveE[i]) f1<<i<<"\n";//выводим в файл
        f1.close();//закрываем поток файла
        delete[] sieveE;//убираем за собой
 
    char be,a;
        cout<<"Начать вывод(Y)?"<<endl;
            cin>>be;
            if(be=='y'||be=='Y')//начало вывода на экран
            {
                    ifstream f1("out.txt");//открываем поток файла на чтение
                    if(!f1)
                        {
                            cout<<"Программа выполнила недопустимую операцию, и будет."<<endl;//обработка отсутствия файла
                        }
                    while(!f1.eof())//выводим до конца файла
                        {
                            f1.get(a);
                            cout<<a;
                        }
                    f1.close();//закрываем поток файла
            }
            else cout<<"Вывод отменён\n";
        cin.get();
}

Заменил вектор на динамеческий массив, т.к. в vc6 std работает медленно. В vc2010 с оптимизацией всё гораздо лучше, но всё равно std работает медленнее обычного c - 20секунд на вывод 100 000 000 через std:ofstream против 15 у обычного

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ