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

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

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

Я тут подумал, посмотрел по теме 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++

#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++

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

@~~alkagolik~~ Заблокирован
	31.07.2012, 16:55	61
	diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	31.07.2012, 17:06	62
	Сообщение от alkagolik diagon, так ты посмотри пост выше. У меня второй тест с выводом в stdout, который я конечно же не копипастил. Так в никсах консоль работает намного быстрее, чем в винде. В любом случае, на рекорд тот код явно не потянет, т.к. алгоритм слишком наивен(примерно O(nlogn) с большой константой). У меня, к примеру, O(nloglogn) с гораздо меньшей константой. Причем с такими ограничениями это, наверное, оптимальный алгоритм, т.к. быстрее решета Эратосфена вроде как только решето Аткина, но у Аткина будет немного выше константа. 0

@~~alkagolik~~ Заблокирован
	31.07.2012, 17:14	63
	diagon, суть не в алгоритме, а в том что alsav22 путает всех своими тестами. Своё видение конкурса я уже сказал. 0

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

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	31.07.2012, 18:42	65
	Сообщение от alkagolik alsav22, что-то ты людей путаешь постоянно. И даже постоянно? Запускаю код в Code Blocks и смотрю, какое время выполнения программы он показывает. И в чём путаю? Добавлено через 1 минуту Сообщение от Dr.Urban Один и тот же код разные компиляторы компилируют по разному. Вы время компиляции проверяете? А я выполнения. Добавлено через 12 минут Нужно тогда договориться, как замер делать. С выводом, без вывода, на какой машине, с какой ОС, каким компилятором компилировать, с какими флагами и т.д. 0

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

@Dr.Urban 63 / 58 / 14 Регистрация: 14.12.2011 Сообщений: 193
	31.07.2012, 19:16	66
	Сообщение от alsav22 Вы время компиляции проверяете? А я выполнения. Кто Вам такое сказал? Я имел ввиду что, программы скомпилированые разными компиляторами, имеют разное время выполнения. Тот же Code::Blocks у меня 1.5с показывал. Кажеться время тему закрывать, одно бла бла бла началось.. 0

alsav22 5498 / 4893 / 831 Регистрация: 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 секунд. Миниатюры 0

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

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

iSeva
	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. На этом свойсте и работает мой алгоритм. Надеюсь сегодня его допишу. Небольшая проблемы в оптимизаци поиска.

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	25.11.2012, 17:32	72
	Сообщение от natalyma Не подскажете почему ваш код в файл выводит числа если задавать N больше 1000 выдает китайские иероглифы ? Не в блокноте, случаем, открываете? У него есть такой баг. 1

@natalyma 0 / 0 / 0 Регистрация: 23.11.2012 Сообщений: 7
	25.11.2012, 17:53	73
	Сообщение от diagon Не в блокноте, случаем, открываете? У него есть такой баг. да в блокноте а в чём надо открывать? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	25.11.2012, 18:09	74
	Сообщение от natalyma да в блокноте а в чём надо открывать? В wordpad'е можно. Еще лучше скачать notepad++. 1

	27.08.2013, 10:51

Опции темы