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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.90
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
#1

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

24.07.2012, 20:30. Просмотров 6546. Ответов 74
Метки нет (Все метки)

Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое!

Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.07.2012, 20:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Конкурс(поиск простых чисел) (C++):

Поиск простых чисел - C++
to idetify if the given K is prime or not. Prime number is the number that can be divided by 1 and by itself ONLY. If given number is...

Поиск простых чисел - C++
Почему мне возвращает просто непарные числа? в чем загвоздка #include <iostream> bool prost(int); using namespace std; int...

Поиск простых чисел - C++
#include <iostream> #include <stdio.h> #include <locale.h> using namespace std; int y; bool m; bool nom( int...

Поиск простых чисел - C++
необходимо найти все простые числа от 1 до 100. Вот я написал код: #include <iostream> #include <string> #include <cstdlib> #include...

Поиск простых чисел - C++
помогите пожалуйста с заданием напишите программу которая при помощи двух вложенных циклов for и оператора вычисления остатка (%) находит...

Поиск простых чисел - C++
3. Разработать программу поиска простых чисел в отрезке (1..N) целых положительных чисел. Программа должна найти и выдать в виде списка все...

74
Endiff
31 / 31 / 1
Регистрация: 19.05.2012
Сообщений: 67
25.07.2012, 03:38 #16
Цитата Сообщение от alsav22 Посмотреть сообщение
То же и у Endiff. 3,1 , но как это читать? Вообще без пробелов. С пробелами - 4,2, с переводом строки 14,8.
Стоп стоп стоп. По-моему, препроцессор удаляет все символы пробела и комментрарии, и коду без разницы, сколько в нем пробелом и комментариев? Не?
0
alsav22
5421 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 04:09 #17
Цитата Сообщение от Endiff Посмотреть сообщение
Стоп стоп стоп. По-моему, препроцессор удаляет все символы пробела и комментрарии, и коду без разницы, сколько в нем пробелом и комментариев? Не?
Имелось ввиду, что при выводе на консоль нет пробелов между числами.
C++
1
2
3
4
5
cout << 2 <<  3 << 5; 
for (i = 6; i <= limit; i++) {
    if (is_prime[i]){
       cout << i;
    }
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 734
25.07.2012, 05:47 #18
господа, решето Эратосфена кто-нибудь пробовал на этой задаче?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 10:46 #19
Цитата Сообщение от salam Посмотреть сообщение
господа, решето Эратосфена кто-нибудь пробовал на этой задаче?
У меня оптимизированная реализация:
Во-первых, проверяются только нечетные числа, это снижает время работы и память в 2 раза.
Во-вторых, просеивание идет только до корня из n, это, опять же, значительно увеличивает производительность.
Ну и в третьих, используется vector< bool >, который отлично сочетается с оптимизациями gcc(в данном случае он работает раза в полтора быстрее, чем обычный массив). Ну и еще он уменьшает память в 8 раз.
0
Small Lamer
142 / 142 / 48
Регистрация: 05.04.2011
Сообщений: 270
25.07.2012, 16:19 #20
Если кому интересно , http://e-maxx.ru/algo/eratosthenes_sieve
1
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
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;
}
0
alsav22
5421 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 23:05 #22
Цитата Сообщение от Small Lamer Посмотреть сообщение
Если кому интересно , http://e-maxx.ru/algo/eratosthenes_sieve
С выводом на консоль - 4,3.
0
diagon
Higher
1929 / 1195 / 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):
1
Вложения
Тип файла: rar sieve.rar (54.6 Кб, 13 просмотров)
alsav22
5421 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.07.2012, 00:44 #24
Результат -1,3.
0
alkagolik
Заблокирован
26.07.2012, 03:43 #25
простые числа, вмещающиеся в int \ long long актуальны?
0
alsav22
5421 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.07.2012, 05:13 #26
Цитата Сообщение от easybudda Посмотреть сообщение
Не претендую на скорость или оригинальность, за то просто:
10 секунд.
0
soon
2541 / 1306 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
26.07.2012, 21:11 #27
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое!
Заметьте, ни слова про время компиляции. Причем верхняя граница явно указана. Это наводит на определенные размышления. Но реализовывать лень.
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
26.07.2012, 23:39 #28
soon, Слишком много шаблонных инстанцирований будет. Не скомпилируется такая раскрутка нигде к сожалению.
1
soon
27.07.2012, 10:10
  #29

Не по теме:

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

0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 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 - падает.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2012, 11:53
Привет! Вот еще темы с ответами:

поиск простых чисел - C++
Как найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является простым числом. Формат входных данных: В...

Поиск простых чисел - C++
Знаю, что тема избитая, но решил написать алгоритм поиска простых чисел. int j,i,k /*количество простых*/ ,nech,prime; ...

Поиск простых чисел на видеоадаптере - C++
Использую CUDA. Для маленьких цифр всё замечательно. С цифрами побольше экран начинает &quot;подмерзать. А при вычислении больше 2 секунд -...

Поиск простых чисел в массиве - C++
Здесь, на форуме для начинающих, была задачка, в которой в матрице A(m,n), состоящей из целых чисел, нужно было найти простые числа (те,...


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
27.07.2012, 11:53
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru