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

@ZaMaZaN4iK · Регистрация: 24.06.2012

Студворк — интернет-сервис помощи студентам

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

Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)

@alkagolik · 31.07.2012, 16:55

diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил.

@diagon · 31.07.2012, 17:06

Сообщение от alkagolik

diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил.

Так в никсах консоль работает намного быстрее, чем в винде.
В любом случае, на рекорд тот код явно не потянет, т.к. алгоритм слишком наивен(примерно O(nlogn) с большой константой). У меня, к примеру, O(nloglogn) с гораздо меньшей константой. Причем с такими ограничениями это, наверное, оптимальный алгоритм, т.к. быстрее решета Эратосфена вроде как только решето Аткина, но у Аткина будет немного выше константа.

@alkagolik · 31.07.2012, 17:14

diagon, суть не в алгоритме, а в том что alsav22 путает всех своими тестами. Своё видение конкурса я уже сказал.

@Dr.Urban · 31.07.2012, 17:16

Один и тот же код разные компиляторы компилируют по разному. Только что проверил в
GNU - время 1-2sec
Borland - время ~ 2-3 sec
VC++ - время >3 sec

alsav22 · 31.07.2012, 18:42

Сообщение от alkagolik

alsav22, что-то ты людей путаешь постоянно.

И даже постоянно? Запускаю код в Code Blocks и смотрю, какое время выполнения программы он показывает. И в чём путаю?

Добавлено через 1 минуту

Сообщение от Dr.Urban

Один и тот же код разные компиляторы компилируют по разному.

Вы время компиляции проверяете? А я выполнения.

Добавлено через 12 минут
Нужно тогда договориться, как замер делать. С выводом, без вывода, на какой машине, с какой ОС, каким компилятором компилировать, с какими флагами и т.д.

@Dr.Urban · 31.07.2012, 19:16

Сообщение от alsav22

Вы время компиляции проверяете? А я выполнения.

Кто Вам такое сказал? Я имел ввиду что, программы скомпилированые разными компиляторами, имеют разное время выполнения. Тот же Code::Blocks у меня 1.5с показывал.

Кажеться время тему закрывать, одно бла бла бла началось..

alsav22 · 31.07.2012, 19:43

Сообщение от Dr.Urban

Кто Вам такое сказал?

Один и тот же код разные компиляторы компилируют по разному. Только что проверил в
GNU - время 1-2sec
Borland - время ~ 2-3 sec
VC++ - время >3 sec

Вы и сказали. Если имели ввиду другое, то так и пишите.

Добавлено через 2 минуты

Сообщение от Dr.Urban

Тот же Code::Blocks у меня 1.5с показывал.

Вы думаете я вас обманываю? Что есть, то и пишу. 15 секунд.

21.11.2012, 20:30

Извиняюсь за вторжение.
У меня есть собственный алгоритм поиска простых чисел, который должен работать на порядки быстрее существующих.
Проблема в том, что я на С++ не программировал с института. Написал прогу на флеше на AS. Можно выложить листинг на AS?

@easybudda · 22.11.2012, 02:14

iSeva, только комментарии поподробнее напишите и описание алгоритма‚ а то заинтриговать получилось‚ но можете непонятым остаться.

22.11.2012, 08:40

Немного поторописля с самим алгоритмом. Вчера отлаживал, есть глюки. Для затравки скажу найденное мной свойство простых чисел, на котором основан алгоритм. Любое нечетное число можно представить в виде разницы квадратов натуральных чисел. Пример 11=6^2-5^2 49=25^2-24^2. Причем как видно числа возводимые в квадрат соседние 6 и 5; 25 и 24. Это свойство справидливо для всех нечетных чисел. Если найдется еще одна пара чисел разница квадратов равна искомому числу, то исходное число не простое. 11 нельзя представить в виде разницы квадратов других чесел значит 11 простое, а вот 49=7^2-0^2. На этом свойсте и работает мой алгоритм. Надеюсь сегодня его допишу. Небольшая проблемы в оптимизаци поиска.

@natalyma · 25.11.2012, 17:31

Сообщение от 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 · 25.11.2012, 17:32

Сообщение от natalyma

Не подскажете почему ваш код в файл выводит числа если задавать N больше 1000 выдает китайские иероглифы ?

Не в блокноте, случаем, открываете? У него есть такой баг.

@natalyma · 25.11.2012, 17:53

Сообщение от diagon

Не в блокноте, случаем, открываете? У него есть такой баг.

да в блокноте

а в чём надо открывать?

@diagon · 25.11.2012, 18:09

Сообщение от natalyma

да в блокноте а в чём надо открывать?

В wordpad'е можно.
Еще лучше скачать notepad++.

27.08.2013, 10:51

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 сек

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5

	Конкурс(поиск простых чисел) 24.07.2012, 20:30. Показов 10518. Ответов 74 Метки нет (Все метки) Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое! Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю) 0

@alkagolik 1599 / 622 / 113 Регистрация: 15.07.2011 Сообщений: 3,548
	31.07.2012, 16:55
	diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил. 0

@alkagolik 1599 / 622 / 113 Регистрация: 15.07.2011 Сообщений: 3,548
	31.07.2012, 17:14
	diagon, суть не в алгоритме, а в том что alsav22 путает всех своими тестами. Своё видение конкурса я уже сказал. 0

@Dr.Urban 63 / 58 / 14 Регистрация: 14.12.2011 Сообщений: 193
	31.07.2012, 17:16
	Один и тот же код разные компиляторы компилируют по разному. Только что проверил в GNU - время 1-2sec Borland - время ~ 2-3 sec VC++ - время >3 sec 0

iSeva
	21.11.2012, 20:30
	Извиняюсь за вторжение. У меня есть собственный алгоритм поиска простых чисел, который должен работать на порядки быстрее существующих. Проблема в том, что я на С++ не программировал с института. Написал прогу на флеше на AS. Можно выложить листинг на AS?

@easybudda Модератор 12843 / 7592 / 1766 Регистрация: 25.07.2009 Сообщений: 13,981
	22.11.2012, 02:14
	iSeva, только комментарии поподробнее напишите и описание алгоритма‚ а то заинтриговать получилось‚ но можете непонятым остаться. 0

iSeva
	22.11.2012, 08:40
	Немного поторописля с самим алгоритмом. Вчера отлаживал, есть глюки. Для затравки скажу найденное мной свойство простых чисел, на котором основан алгоритм. Любое нечетное число можно представить в виде разницы квадратов натуральных чисел. Пример 11=6^2-5^2 49=25^2-24^2. Причем как видно числа возводимые в квадрат соседние 6 и 5; 25 и 24. Это свойство справидливо для всех нечетных чисел. Если найдется еще одна пара чисел разница квадратов равна искомому числу, то исходное число не простое. 11 нельзя представить в виде разницы квадратов других чесел значит 11 простое, а вот 49=7^2-0^2. На этом свойсте и работает мой алгоритм. Надеюсь сегодня его допишу. Небольшая проблемы в оптимизаци поиска.