Форум программистов, компьютерный форум 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)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 02:46     Конкурс(поиск простых чисел) #41
Доработал. Работает за 1.326

http://zalil.ru/33624008

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

Не по теме:

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

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

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

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


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

Добавлено через 1 минуту
И, между прочим, компилится довольно быстро. Даже очень.
13 секунд.
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
30.07.2012, 05:52     Конкурс(поиск простых чисел) #45
alsav22, компиляция или выполнение?
и на каких характеристиках компьютера?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
30.07.2012, 06:30     Конкурс(поиск простых чисел) #46
Цитата Сообщение от Ksan Посмотреть сообщение
Доработал. Работает за 1.326

http://zalil.ru/33624008

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

Не по теме:

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

12 секунд.

Добавлено через 6 минут
Цитата Сообщение от Ksan Посмотреть сообщение
alsav22, компиляция или выполнение?
и на каких характеристиках компьютера?
Выполнение. Компиляция - секунды. Посмотрите в предыдущих постах за сколько другие варианты выполнялись (особенно у diagon), при тех же характеристиках компа. (два ядра 3,21ГГц, ОЗУ 4Гб). Перевод строки замедляет выполнение, больше чем, в 3 раза . Нужно через пробел выводить.
xADMIRALx
 Аватар для xADMIRALx
66 / 60 / 1
Регистрация: 09.06.2012
Сообщений: 291
30.07.2012, 07:56     Конкурс(поиск простых чисел) #47
alsav22, вить в задание не указано что нежен пробел или перевод строки
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
30.07.2012, 09:10     Конкурс(поиск простых чисел) #48
Цитата Сообщение от xADMIRALx Посмотреть сообщение
alsav22, вить в задание не указано что нежен пробел или перевод строки
И что? Конкурс в чём? Сделать код как можно более бысрым и, разумеется, чтобы числа можно было прочесть. Я просто написал, что перевод строки замедляет вывод. И чтобы с другими выриантами можно было сравнивать.
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
30.07.2012, 23:45     Конкурс(поиск простых чисел) #49
Знатоки, просветите, пожалуйста, как находят, например, числа Мерсенна? Я имею в виду, чисто алгоритмически, как это делается? И почему это делают с помощью распределённых вычислений,- они находят, а потом проверяют его, что-ли?
alkagolik
31.07.2012, 02:47
  #50

Не по теме:

#pragma, юморишь?

#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
31.07.2012, 02:52     Конкурс(поиск простых чисел) #51
Нет, я честно не знаю. Ну есть формула 2^n-1 - так и ищут, а потом проверяют, или есть более простые способы? Просто мне кажется странным факт из Википедии, что на данный момент известно лишь 47 чисел Мерсенна

Не по теме:

интересно ещё, как у них числа таких порядков хранятся, в которых по 10 млн цифр..

alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.07.2012, 03:10     Конкурс(поиск простых чисел) #52
#pragma, не http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n} - 1 , а http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{p} - 1, р - простое число. Проверяется с помощью теста Люка — Лемера. Ничего странного тут нет, наибольшее известное число Мерсена http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{43,112,609} - 1 на минуточку...
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
31.07.2012, 03:15     Конкурс(поиск простых чисел) #53
alkagolik, Спасибо , я просто неправильно понял написанное )
То есть
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, … (последовательность A001348 в OEIS)
в этой последовательности не обязательно все числа простые, а только некоторые?
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.07.2012, 03:40     Конкурс(поиск простых чисел) #54
#pragma, в ней все числа простые. Но, это простые числа Мерсена, полученные с помощью формулы выше и прошедшие тест на простоту.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.07.2012, 12:45     Конкурс(поиск простых чисел) #55
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
#include <iostream>
#include <math.h>
using namespace std;
 
#define N 300000
int main()
{
    int count = 1;
    int mass[26000] = {1,2};    // ~26000 simple numbers 1..300k 
    bool flag = false;
 
    for(int i = 3 ; i < N ; i += 2 )
    {
        flag = true;
 
        for(int j = 2 ; j < count ; j++)
        {
            if(!(i % mass[j]) )
            {
                flag = false;
                break;
            }
            else if(mass[j] >= sqrt(i))
            {
                break;
            }
 
        }
 
        if(flag)
        {
            cout << i << endl;
            mass[++count] = i;
        }
    }
    return 0;
}
Миниатюры
Конкурс(поиск простых чисел)  
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 14:05     Конкурс(поиск простых чисел) #56
15 секунд.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.07.2012, 14:55     Конкурс(поиск простых чисел) #57
Это время исполнения 15 сек? на какой машине?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 16:03     Конкурс(поиск простых чисел) #58
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Это время исполнения 15 сек? на какой машине?
Смотрите 46 пост.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.07.2012, 16:45     Конкурс(поиск простых чисел) #59
alsav22, что-то ты людей путаешь постоянно.
время
Bash
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
62
63
64
65
66
67
68
indicator@pc-host:~$ cat test.cc
#include <iostream>
#include <math.h>
using namespace std;
 
#define N 300000
int main()
{
    int count = 1;
    int mass[26000] = {1,2};    // ~26000 simple numbers 1..300k 
    bool flag = false;
 
    for(int i = 3 ; i < N ; i += 2 )
    {
        flag = true;
 
        for(int j = 2 ; j < count ; j++)
        {
            if(!(i % mass[j]) )
            {
                flag = false;
                break;
            }
            else if(mass[j] >= sqrt(i))
            {
                break;
            }
 
        }
 
        if(flag)
        {
            cout << i << endl;
            mass[++count] = i;
        }
    }
    return 0;
}
indicator@pc-host:~$ g++ -s -O2 test.cc -o test
indicator@pc-host:~$ time ./test > file
 
real    0m0.166s
user    0m0.044s
sys 0m0.116s
indicator@pc-host:~$ time ./test
...
real    0m0.408s
user    0m0.052s
sys 0m0.096s
indicator@pc-host:~$ lscpu
Architecture:          i686
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 15
Stepping:              13
CPU MHz:               1200.000
BogoMIPS:              4400.22
L1d cache:             32K
L1i cache:             32K
L2 cache:              2048K
indicator@pc-host:~$
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 16:52     Конкурс(поиск простых чисел)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2012, 16:52     Конкурс(поиск простых чисел) #60
Цитата Сообщение от alkagolik Посмотреть сообщение
alsav22, что-то ты людей путаешь постоянно
Он же тестирует с выводом на консоль)
Банально посчитать простые числа до 300 000 тривиально, это делается за несколько миллисекунд, однако вывод на консоль занимает секунд 5.
Собственно, в моей программке почти незаметная пауза перед выводом - это вычисление всех простых чисел и забивание их в строку, дальше я просто вывожу эту строку с помощью fwrite(пробовал через writefile из winapi, но он почему-то отказывался выводить более-менее длинные строки).
Yandex
Объявления
31.07.2012, 16:52     Конкурс(поиск простых чисел)
Ответ Создать тему
Опции темы

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