Форум программистов, компьютерный форум 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)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.07.2012, 16:55     Конкурс(поиск простых чисел) #61
diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2012, 17:06     Конкурс(поиск простых чисел) #62
Цитата Сообщение от alkagolik Посмотреть сообщение
diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил.
Так в никсах консоль работает намного быстрее, чем в винде.
В любом случае, на рекорд тот код явно не потянет, т.к. алгоритм слишком наивен(примерно O(nlogn) с большой константой). У меня, к примеру, O(nloglogn) с гораздо меньшей константой. Причем с такими ограничениями это, наверное, оптимальный алгоритм, т.к. быстрее решета Эратосфена вроде как только решето Аткина, но у Аткина будет немного выше константа.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.07.2012, 17:14     Конкурс(поиск простых чисел) #63
diagon, суть не в алгоритме, а в том что alsav22 путает всех своими тестами. Своё видение конкурса я уже сказал.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.07.2012, 17:16     Конкурс(поиск простых чисел) #64
Один и тот же код разные компиляторы компилируют по разному. Только что проверил в
GNU - время 1-2sec
Borland - время ~ 2-3 sec
VC++ - время >3 sec
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 18:42     Конкурс(поиск простых чисел) #65
Цитата Сообщение от alkagolik Посмотреть сообщение
alsav22, что-то ты людей путаешь постоянно.
И даже постоянно? Запускаю код в Code Blocks и смотрю, какое время выполнения программы он показывает. И в чём путаю?

Добавлено через 1 минуту
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Один и тот же код разные компиляторы компилируют по разному.
Вы время компиляции проверяете? А я выполнения.

Добавлено через 12 минут
Нужно тогда договориться, как замер делать. С выводом, без вывода, на какой машине, с какой ОС, каким компилятором компилировать, с какими флагами и т.д.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.07.2012, 19:16     Конкурс(поиск простых чисел) #66
Цитата Сообщение от alsav22 Посмотреть сообщение
Вы время компиляции проверяете? А я выполнения.
Кто Вам такое сказал? Я имел ввиду что, программы скомпилированые разными компиляторами, имеют разное время выполнения. Тот же Code::Blocks у меня 1.5с показывал.

Кажеться время тему закрывать, одно бла бла бла началось..
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
31.07.2012, 19:43     Конкурс(поиск простых чисел) #67
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Кто Вам такое сказал?
Один и тот же код разные компиляторы компилируют по разному. Только что проверил в
GNU - время 1-2sec
Borland - время ~ 2-3 sec
VC++ - время >3 sec
Вы и сказали. Если имели ввиду другое, то так и пишите.

Добавлено через 2 минуты
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Тот же Code::Blocks у меня 1.5с показывал.
Вы думаете я вас обманываю? Что есть, то и пишу. 15 секунд.
Миниатюры
Конкурс(поиск простых чисел)  
iSeva
Сообщений: n/a
21.11.2012, 20:30     Конкурс(поиск простых чисел) #68
Извиняюсь за вторжение.
У меня есть собственный алгоритм поиска простых чисел, который должен работать на порядки быстрее существующих.
Проблема в том, что я на С++ не программировал с института. Написал прогу на флеше на AS. Можно выложить листинг на AS?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
22.11.2012, 02:14     Конкурс(поиск простых чисел) #69
iSeva, только комментарии поподробнее напишите и описание алгоритма‚ а то заинтриговать получилось‚ но можете непонятым остаться.
iSeva
Сообщений: n/a
22.11.2012, 08:40     Конкурс(поиск простых чисел) #70
Немного поторописля с самим алгоритмом. Вчера отлаживал, есть глюки. Для затравки скажу найденное мной свойство простых чисел, на котором основан алгоритм. Любое нечетное число можно представить в виде разницы квадратов натуральных чисел. Пример 11=6^2-5^2 49=25^2-24^2. Причем как видно числа возводимые в квадрат соседние 6 и 5; 25 и 24. Это свойство справидливо для всех нечетных чисел. Если найдется еще одна пара чисел разница квадратов равна искомому числу, то исходное число не простое. 11 нельзя представить в виде разницы квадратов других чесел значит 11 простое, а вот 49=7^2-0^2. На этом свойсте и работает мой алгоритм. Надеюсь сегодня его допишу. Небольшая проблемы в оптимизаци поиска.
natalyma
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 7
25.11.2012, 17:31     Конкурс(поиск простых чисел) #71
Цитата Сообщение от diagon Посмотреть сообщение
Писал когда-то.
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
#include <vector>
#include <cstdio> 
 
int main()
{   
    freopen("output.txt", "w", stdout);
 
    const int n = 1e8;
    
    std::vector< bool > sieve( (n >> 1) + 1);
    
    if ( n >= 2 )
        printf("2 ");
 
    int i = 3;
 
    for (; i * i <= n; i += 2)
    {
        if ( !sieve[i >> 1] )
        {
            printf("%d ", i);
 
            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] )
        {
            printf("%d ", i);
        }
    }
}
Крайне желательно использовать с оптимизациями gcc(которые очень сильно разгоняют vector<bool>). Если нету gcc, то лучше заменить vector< bool > на vector< int >. У меня для n = 10^8 отработало за 6 секунд( 2 ядра по 1.6гц каждый ).
Можно еще многопоточность прикрутить, но мне лень =\
Не подскажете почему ваш код в файл выводит числа если задавать N больше 1000 выдает китайские иероглифы ?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.11.2012, 17:32     Конкурс(поиск простых чисел) #72
Цитата Сообщение от natalyma Посмотреть сообщение
Не подскажете почему ваш код в файл выводит числа если задавать N больше 1000 выдает китайские иероглифы ?
Не в блокноте, случаем, открываете? У него есть такой баг.
natalyma
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 7
25.11.2012, 17:53     Конкурс(поиск простых чисел) #73
Цитата Сообщение от diagon Посмотреть сообщение
Не в блокноте, случаем, открываете? У него есть такой баг.
да в блокноте а в чём надо открывать?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.11.2012, 18:09     Конкурс(поиск простых чисел) #74
Цитата Сообщение от natalyma Посмотреть сообщение
да в блокноте а в чём надо открывать?
В wordpad'е можно.
Еще лучше скачать notepad++.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2013, 10:51     Конкурс(поиск простых чисел)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
bert_
Сообщений: n/a
27.08.2013, 10:51     Конкурс(поиск простых чисел) #75
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
  int main()
{   int i,j,k,NM,b=300000;
    NM = (int)b/4;
int *M = new int [NM+1]; printf("\nstart\n");
    M[0]=2;j=0;
    for (i = 3; i <= b; i=i+2)
    { j++; M[j]=i; 
      for (k = 0; M[k]*M[k] <= i; k++) if (i%M[k]== 0) {j--;break;}
    }
    printf("\n");for (i = 0; i <=j; i++) printf("%i, ",M[i]);
    printf("\nProstyh chisel %i \n",j+1); 
   delete []M; system("pause"); return 0;
}
до 300000 на экран за 1.88 сек.

Добавлено через 17 минут
до 10^8 в файл за 43 сек
Yandex
Объявления
27.08.2013, 10:51     Конкурс(поиск простых чисел)
Ответ Создать тему
Опции темы

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