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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.74
1234569
5 / 5 / 1
Регистрация: 25.11.2010
Сообщений: 23
14.12.2010, 12:52     Решето Эратосфена #1
Определить простые числа методом просеивания с помощью <<решета Эратосфена>> с _битовой упаковкой_ данных при сохранении.

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] на ложность, но от чего?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.12.2010, 12:52     Решето Эратосфена
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
1234569
5 / 5 / 1
Регистрация: 25.11.2010
Сообщений: 23
17.12.2010, 00:29  [ТС]     Решето Эратосфена #2
Добавил вывод в файл и вывод из файла:
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
5 / 5 / 1
Регистрация: 25.11.2010
Сообщений: 23
18.12.2010, 21:54  [ТС]     Решето Эратосфена #3
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 у обычного
Yandex
Объявления
18.12.2010, 21:54     Решето Эратосфена
Ответ Создать тему
Опции темы

Текущее время: 19:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru