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

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

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

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

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

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

Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)
Лучшие ответы (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) целых положительных чисел. Программа должна найти и выдать в виде списка все...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
soon
2540 / 1305 / 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
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:01 #33
Раз уж о времени компиляции не говорили. А лишь о времени выдачи. И вообще.
Вообщем, извратился.

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

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


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

Добавлено через 1 минуту
И, между прочим, компилится довольно быстро. Даже очень.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
30.07.2012, 02:23 #34
Ksan, Да вы однако не ленивый, но это никак не решение задачи)
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:25 #35
ForEveR, обоснуйте, почему это не решение?

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

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

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


так что, решение
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
30.07.2012, 02:27 #36
программу, вычисляющую простые числа от 1 до 300000
Однако false. Я не вижу вычислений. Я вижу тупо вывод всех простых чисел от 1 до 3000000
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:29 #37
ForEveR, хорошо, я перед каждым допишу +2 - 1 - 1
чем не вычисление?
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
30.07.2012, 02:35 #38
Ksan, Да не стоит извращаться. Лучше бы compile-time алгоритм придумали, чем ересью заниматься.
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:37 #39
ForEveR, почему же бд ты считаешь ересью?)
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
30.07.2012, 02:38 #40
Ksan, Я че-то не узрел здесь БД.

Не по теме:

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

Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:46 #41
Доработал. Работает за 1.326

http://zalil.ru/33624008

Добавлено через 29 секунд

Не по теме:

ForEveR, ищи письмо в лс

xADMIRALx
67 / 61 / 1
Регистрация: 09.06.2012
Сообщений: 291
30.07.2012, 03:50 #42
Ksan, Не соответствует заданию
написать программу, вычисляющую простые числа от 1 до 300000
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 05:51 #43
xADMIRALx, я же уже написал
припишу что-нибудь вроде n+1-3+2
вот, пожалуйста: вычисление
alsav22
5417 / 4813 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
30.07.2012, 05:52 #44
Цитата Сообщение от Ksan Посмотреть сообщение
Раз уж о времени компиляции не говорили. А лишь о времени выдачи. И вообще.
Вообщем, извратился.

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

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


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

Добавлено через 1 минуту
И, между прочим, компилится довольно быстро. Даже очень.
13 секунд.
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 05:52 #45
alsav22, компиляция или выполнение?
и на каких характеристиках компьютера?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2012, 05:52
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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