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

Конкурс(поиск простых чисел) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.90
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
24.07.2012, 20:30     Конкурс(поиск простых чисел) #1
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое!

Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.07.2012, 17:37     Конкурс(поиск простых чисел) #21
Не претендую на скорость или оригинальность, за то просто:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
 
const int TOP(300000);
 
int main() {
    std::vector<int> vec(1, 2);
    int i;
    
    for ( int current = 3; current <= TOP; current += 2 ) {
        for ( i = 1; i < vec.size(); ++i )
            if ( ! ( current % vec[i] ) )
                break;
        if ( i == vec.size() )
            vec.push_back(current);
    }
    
    for ( i = 0; i < vec.size(); ++i )
        std::cout << vec[i] << ' ';
    
    std::cout << std::endl;
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 23:05     Конкурс(поиск простых чисел) #22
Цитата Сообщение от Small Lamer Посмотреть сообщение
Если кому интересно , http://e-maxx.ru/algo/eratosthenes_sieve
С выводом на консоль - 4,3.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.07.2012, 00:20     Конкурс(поиск простых чисел) #23
Ну, если уж подстраиваться под вывод, то так
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
#include <vector>
#include <cstdio> 
#include <ctime>
#include <cstdlib>
 
const int buf_size = 1e6;
char buffer[buf_size + 15] = "2 ";
 
int main()
{   
    int cur_len = 2;
 
    puts("Enter n : ");
    int n;
    scanf("%d", &n);
 
    time_t now = clock();
 
    std::vector< bool > sieve( (n >> 1) + 1);
 
    int i = 3;
 
    for (; i * i <= n; i += 2)
    {
        if ( !sieve[i >> 1] )
        {
            cur_len += sprintf(buffer + cur_len, "%d ", i);
            
            if ( cur_len > buf_size )
            {
                fwrite( (void *) buffer, 1, cur_len, stdout );
                cur_len = 0;
            }
            
 
            for (int j = (i << 1); j <= n; j += i)
                if ( j & 1 )
                    sieve[j >> 1] = 1;
        }
    }
    
    for (; i <= n; i += 2)
    {
        if ( !sieve[i >> 1] )
        {
            cur_len += sprintf(buffer + cur_len, "%d ", i);
            
            if ( cur_len > buf_size )
            {
                fwrite( (void *) buffer, 1, cur_len, stdout );
                cur_len = 0;
            }
        }
    }
 
    fwrite( (void *) buffer, 1, cur_len, stdout );
 
    printf("\nTime : %lf\n",  1. * (clock() - now) / CLOCKS_PER_SEC);
    getchar();
    getchar();
}
Скомпилированный вариант(компилировал в gcc с флагами -O3 -fwhole-program):
Вложения
Тип файла: rar sieve.rar (54.6 Кб, 13 просмотров)
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.07.2012, 00:44     Конкурс(поиск простых чисел) #24
Результат -1,3.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
26.07.2012, 03:43     Конкурс(поиск простых чисел) #25
простые числа, вмещающиеся в int \ long long актуальны?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.07.2012, 05:13     Конкурс(поиск простых чисел) #26
Цитата Сообщение от easybudda Посмотреть сообщение
Не претендую на скорость или оригинальность, за то просто:
10 секунд.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
26.07.2012, 21:11     Конкурс(поиск простых чисел) #27
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое!
Заметьте, ни слова про время компиляции. Причем верхняя граница явно указана. Это наводит на определенные размышления. Но реализовывать лень.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
26.07.2012, 23:39     Конкурс(поиск простых чисел) #28
soon, Слишком много шаблонных инстанцирований будет. Не скомпилируется такая раскрутка нигде к сожалению.
soon
27.07.2012, 10:10
  #29

Не по теме:

ForEveR, а как посчитать требуемый объем RAM? Сложить занимаемую память всех создаваемых структур?

ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
27.07.2012, 11:53     Конкурс(поиск простых чисел) #30
soon, Не отвечу на этот вопрос. Но тут даже не в этом дело. Компиляторы устанавливают ограничения на раскрутку шаблонов. Их вроде можно переставлять, но как-то это не комильфо что-ли.

Не по теме:

Вчера запустил одну прогу (подсчет чисел простых как раз и их печать, от 0 до 3000 на шаблонах времени компиляции) - компилировалось около получаса-часа, а потом резко выжрало всю доступную память.



C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
template<int Begin, int N>
struct Some
{
   static constexpr int value = Begin + Some<Begin + 1, N>::value;
};
 
template<int N>
struct Some<N, N>
{
   static constexpr int value = N;
};
 
int main()
{
   std::cout << Some<0, 50000>::value << std::endl;
}
Bash
1
2
3
forever@pterois:~/My_pro1/cpp_pro$ g++ -o new new.cpp -std=c++0x -ftemplate-depth=300000
forever@pterois:~/My_pro1/cpp_pro$ ./new 
1250025000
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
template<int Begin, int N>
struct Some
{
   static constexpr int64_t value = Begin + Some<Begin + 1, N>::value;
};
 
template<int N>
struct Some<N, N>
{
   static constexpr int64_t value = N;
};
 
int main()
{
   std::cout << Some<0, 100000>::value << std::endl;
}
Bash
1
2
3
4
5
forever@pterois:~/My_pro1/cpp_pro$ g++ -o new new.cpp -std=c++0x -ftemplate-depth=300000
g++: внутренняя ошибка компилятора: Ошибка сегментирования (program cc1plus)
Отправьте подробное сообщение об ошибке
с препроцессированным исходным кодом.
Смотрите инструкции в <file:///usr/share/doc/gcc-4.6/README.Bugs>.
Добавлено через 20 минут
Опытным путем было выяснено, что gcc4.6 держит максимум такое выражение.

C++
1
std::cout << Some<0, 89224>::value << std::endl;
На 89225 - падает.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
27.07.2012, 13:01     Конкурс(поиск простых чисел) #31
Цитата Сообщение от ForEveR Посмотреть сообщение
Компиляторы устанавливают ограничения на раскрутку шаблонов. Их вроде можно переставлять, но как-то это не комильфо что-ли.
Это обходил через -ftemplate-depth. Но читал где-то, что есть вероятность корявой сборки программы.

Цитата Сообщение от ForEveR Посмотреть сообщение
Вчера запустил одну прогу (подсчет чисел простых как раз и их печать, от 0 до 3000 на шаблонах времени компиляции) - компилировалось около получаса-часа, а потом резко выжрало всю доступную память.
Тоже самое. 1.7 RAM, поработало минут 20 на этом и завершилось.

Добавлено через 25 минут
Цитата Сообщение от ForEveR Посмотреть сообщение
Опытным путем было выяснено, что gcc4.6 держит максимум такое выражение.
4.7.1, второй код отработал без проблем
Bash
1
2
3
4
5
g++ -c -Wall -D_GLIBCXX_USE_NANOSLEEP -O3 -ftemplate-depth=600000 --std=gnu++11 main.cpp -o main.o
g++ main.o -lm -lboost_regex -lboost_filesystem -lboost_system -lboost_timer -lboost_date_time -lboost_thread -o main
[Finished in 622.4s]
soon@desktop:~/Src/C++/main$ ./main 
5000050000
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
29.07.2012, 23:53     Конкурс(поиск простых чисел) #32
ЭЭЭ тут простое решето эратосфена на консоль без оптимизаций у меня меньше чем за 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
#include <cstdio>
#include <vector>
 
using namespace std;
 
int main()
{
    int n;
    scanf("%d", &n);
    vector <bool> pr(n, true);
    pr[0] = false;
    pr[1] = false;
    printf("%d ", 2);
    for (int i = 3; i <= n; i++)
        {
            if (i % 2 == 0)
                pr[i] = false;
            else
                {
                    if (pr[i])
                        {
                            printf("%d ", i);
                            for (long long j = i * 1ll* i; j <= n; j += i)
                                pr[j] = false;
                        }
                }
        }
    return 0;
}
Добавлено через 28 минут
были оказывается тут уже похожие реализации)
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:01     Конкурс(поиск простых чисел) #33
Раз уж о времени компиляции не говорили. А лишь о времени выдачи. И вообще.
Вообщем, извратился.

Время на все про все заняло "2.558"

как таковая библиотека нужна только одна: stdio.h
остальные для вывода времени и что бы не вылетала консоль


Уж не поленитесь, скачайте. Форум печатать отказался.
http://zalil.ru/33623938

Добавлено через 1 минуту
И, между прочим, компилится довольно быстро. Даже очень.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
30.07.2012, 02:23     Конкурс(поиск простых чисел) #34
Ksan, Да вы однако не ленивый, но это никак не решение задачи)
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:25     Конкурс(поиск простых чисел) #35
ForEveR, обоснуйте, почему это не решение?

программу, вычисляющую простые числа от 1 до 300000
true

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Программа ДОЛЖНА работать за 6 секунд
true

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Обьем памяти неограничен
true


так что, решение
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
30.07.2012, 02:27     Конкурс(поиск простых чисел) #36
программу, вычисляющую простые числа от 1 до 300000
Однако false. Я не вижу вычислений. Я вижу тупо вывод всех простых чисел от 1 до 3000000
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:29     Конкурс(поиск простых чисел) #37
ForEveR, хорошо, я перед каждым допишу +2 - 1 - 1
чем не вычисление?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
30.07.2012, 02:35     Конкурс(поиск простых чисел) #38
Ksan, Да не стоит извращаться. Лучше бы compile-time алгоритм придумали, чем ересью заниматься.
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:37     Конкурс(поиск простых чисел) #39
ForEveR, почему же бд ты считаешь ересью?)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2012, 02:38     Конкурс(поиск простых чисел)
Еще ссылки по теме:

Поиск простых чисел C++
C++ Поиск простых чисел
Поиск простых чисел C++

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
30.07.2012, 02:38     Конкурс(поиск простых чисел) #40
Ksan, Я че-то не узрел здесь БД.

Не по теме:

Вообще разговор несколько отошел от темы, хочешь обсудить, является твой код бредом или нет - велкам в личку.

Yandex
Объявления
30.07.2012, 02:38     Конкурс(поиск простых чисел)
Ответ Создать тему
Опции темы

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