С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

24.07.2012, 20:30. Просмотров 6656. Ответов 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
alsav22
5428 / 4823 / 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 раза . Нужно через пробел выводить.
0
xADMIRALx
67 / 61 / 1
Регистрация: 09.06.2012
Сообщений: 291
30.07.2012, 07:56 #47
alsav22, вить в задание не указано что нежен пробел или перевод строки
0
alsav22
5428 / 4823 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
30.07.2012, 09:10 #48
Цитата Сообщение от xADMIRALx Посмотреть сообщение
alsav22, вить в задание не указано что нежен пробел или перевод строки
И что? Конкурс в чём? Сделать код как можно более бысрым и, разумеется, чтобы числа можно было прочесть. Я просто написал, что перевод строки замедляет вывод. И чтобы с другими выриантами можно было сравнивать.
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
30.07.2012, 23:45 #49
Знатоки, просветите, пожалуйста, как находят, например, числа Мерсенна? Я имею в виду, чисто алгоритмически, как это делается? И почему это делают с помощью распределённых вычислений,- они находят, а потом проверяют его, что-ли?
0
alkagolik
31.07.2012, 02:47
  #50

Не по теме:

#pragma, юморишь?

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

Не по теме:

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

0
alkagolik
Заблокирован
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 на минуточку...
1
#pragma
Временно недоступен
954 / 225 / 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)
в этой последовательности не обязательно все числа простые, а только некоторые?
0
alkagolik
Заблокирован
31.07.2012, 03:40 #54
#pragma, в ней все числа простые. Но, это простые числа Мерсена, полученные с помощью формулы выше и прошедшие тест на простоту.
0
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;
}
0
Миниатюры
Конкурс(поиск простых чисел)  
alsav22
5428 / 4823 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 14:05 #56
15 секунд.
0
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.07.2012, 14:55 #57
Это время исполнения 15 сек? на какой машине?
0
alsav22
5428 / 4823 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 16:03 #58
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Это время исполнения 15 сек? на какой машине?
Смотрите 46 пост.
0
alkagolik
Заблокирован
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:~$
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2012, 16:52 #60
Цитата Сообщение от alkagolik Посмотреть сообщение
alsav22, что-то ты людей путаешь постоянно
Он же тестирует с выводом на консоль)
Банально посчитать простые числа до 300 000 тривиально, это делается за несколько миллисекунд, однако вывод на консоль занимает секунд 5.
Собственно, в моей программке почти незаметная пауза перед выводом - это вычисление всех простых чисел и забивание их в строку, дальше я просто вывожу эту строку с помощью fwrite(пробовал через writefile из winapi, но он почему-то отказывался выводить более-менее длинные строки).
0
31.07.2012, 16:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 16:52
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Опции темы

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