Форум программистов, компьютерный форум 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)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.07.2012, 20:34     Конкурс(поиск простых чисел) #2
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.
Эм, это ее надо максимально затормаживать что ли?
От 1 до 10^8 можно за секунду найти(если использовать реализацию одного из авторов решета Аткина).
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
24.07.2012, 20:37  [ТС]     Конкурс(поиск простых чисел) #3
Нет, я имел ввиду, что программа должна работать за 6 секунд и менее.Вы так думаете, что найти это очень быстро, вы код напишите и проверьте)
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
24.07.2012, 20:37     Конкурс(поиск простых чисел) #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
 
int main() {
    const int n = 300000;
    std::vector <bool> prime(n+1, true);
    prime[0] = prime[1] = false;
    for(int i = 2; i <= n; ++i) {
        if (prime[i]) {
            std::cout << i << " ";
            if (1ll * i * i <= n)
                for(int j = i * i; j <= n; j += i)
                    prime[j] = false;
        }
    }
    return 0;
}
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
24.07.2012, 20:38     Конкурс(поиск простых чисел) #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
inline int simple(int x)
{
    for (int i = 2; i < x; i++)
        if ((x % i) == 0)
            return 0;
    return 1;
}
 
int main()
{
    cout << "1/n3/n";
    for (int i = 4; i < 300000; i++)
        if (simple(i))
            cout << i << endl;
            
    system("PAUSE > NULL");
}
ага, может и не за 6
Intel~lect
 Аватар для Intel~lect
135 / 124 / 2
Регистрация: 03.07.2012
Сообщений: 355
24.07.2012, 20:44     Конкурс(поиск простых чисел) #6
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
#include <iostream>
#include <windows.h>
#include <cmath>
 
using namespace std;
 
int is_prostoe(int n);
 
int main()
{
    for (int n=1; n<=300000; n++)
        if ( is_prostoe(n) )
            cout << n << endl;
 
 
    cout << endl;
    system("pause");
    return 0;
}
 
 
int is_prostoe(int n)
{
    double n_sqrt = sqrt(n);
 
    for (int i=2; i<=n_sqrt; i++)
        if (n % i == 0)
            return 0;
 
    return 1;
}
67 секунд
Endiff
 Аватар для Endiff
30 / 30 / 1
Регистрация: 19.05.2012
Сообщений: 67
24.07.2012, 20:59     Конкурс(поиск простых чисел) #7
Решето Аткина так и никто не вспомнил...
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
 
using std::cout;
using std::cin;
using std::endl;
 
int main() {
long int limit = 300000;
int sqr_lim;
bool is_prime[300001];
int x2, y2;
int i, j;
int n;
 
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
    x2 += 2 * i - 1;
    y2 = 0;
    for (j = 1; j <= sqr_lim; j++) {
        y2 += 2 * j - 1;
 
        n = 4 * x2 + y2;
        if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
            is_prime[n] = !is_prime[n];
        n -= x2;
        if ((n <= limit) && (n % 12 == 7))
            is_prime[n] = !is_prime[n];
        n -= 2 * y2;
        if ((i > j) && (n <= limit) && (n % 12 == 11))
            is_prime[n] = !is_prime[n];
    }
}
for (i = 5; i <= sqr_lim; i++) {
    if (is_prime[i]) {
        n = i * i;
        for (j = n; j <= limit; j += n) {
            is_prime[j] = false;
        }
    }
}
cout << 2 <<  3 << 5; 
for (i = 6; i <= limit; i++) {
    if (is_prime[i]){
       cout << i;
    }
}
}

Не по теме:

А нет, простите, один вспомнил

neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
24.07.2012, 21:00     Конкурс(поиск простых чисел) #8
diagon вспомнил
Endiff
 Аватар для Endiff
30 / 30 / 1
Регистрация: 19.05.2012
Сообщений: 67
24.07.2012, 21:01     Конкурс(поиск простых чисел) #9
Цитата Сообщение от neske Посмотреть сообщение
diagon вспомнил
Уже увидел, простите
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.07.2012, 21:05     Конкурс(поиск простых чисел) #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Давно писал. Примерно 0.022 у меня.

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
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <ctime>
 
template<int N>
size_t get_next_unchecked(const bool (&s)[N], const size_t current_idx)
{
   // Ищем первый элемент == false, начиная с адреса s + current_idx + 1, до конца массива.
   const bool* pointer = std::find(s + current_idx + 1, s + N, false);
   // Если мы не нашли таких элементов - возвращаем 0, иначе возвращаем разницу между указателем и началом массива
   // т.е. порядковый номер элемента.
   return (pointer == s + N) ? 0 : pointer - s;
}
 
int main()
{
   const size_t max = 300000;
   bool checked[max] = {true, true, false};
   size_t current_idx = 2;
   time_t now = clock();
   // Цикл начинается с двух и идет до тех пор пока i меньше max и i != 0, 
   // каждая итерация цикла i будет равно следующему индексу, возвращенному из get_next_unchecked,
   // и current_idx будет равен i.
   // Т.е.
   // i = 2. Начало цикла. Просто пробегаем вторым циклом по массиву начиная от 4, прибавляя 2. Цикл закончился.
   // теперь получаем i из get_next_unchecked - это будет 3, таким образом i = 3, current_idx = 3.
   // Пробежали по циклу от 9 до max прибавляя 3. Снова получаем i из get_next_unchecked это будет 5. и т.д.
   for (size_t i = current_idx; i < max && i; i = get_next_unchecked(checked, current_idx), current_idx = i)
   {
      for (size_t j = i * i; j < max; j += i)
      {
         checked[j] = true;
      }
   }
   /*for (size_t i = 2; i < max; ++i)
   {
       if (!checked[i])
       {
          std::cout << i << " ";
       }
   }
   std::cout << std::endl;*/
   std::cout << "Time: " << static_cast<double>(clock() - now) / CLOCKS_PER_SEC << std::endl;
}
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 00:12     Конкурс(поиск простых чисел) #11
Цитата Сообщение от Intel~lect Посмотреть сообщение
67 секунд
У меня за 15. Кстати, перевод строки больше чем в 3 раза замедляет. Intel~lect, если у вас сделать вывод через пробел, то 4,3. У neske, если так:
C++
1
std::cout << i << " ";
, то за 4, если так:
C++
1
std::cout << i << '\n';
, то за 14.

То же и у Endiff. 3,1 , но как это читать? Вообще без пробелов. С пробелами - 4,2, с переводом строки 14,8.

У уважаемого ForEveR быстро, конечно, если без вывода - 0,078. Если с выводом - 5.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 00:21     Конкурс(поиск простых чисел) #12
Писал когда-то.
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гц каждый ).
Можно еще многопоточность прикрутить, но мне лень =\
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 00:42     Конкурс(поиск простых чисел) #13
diagon, что-то этот код не хочет работать.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 00:47     Конкурс(поиск простых чисел) #14
Цитата Сообщение от alsav22 Посмотреть сообщение
diagon, что-то этот код не хочет работать.
А что говорит?
P.S. если что, у меня вывод идет в файл "output.txt", потому что банально вывод всех простых чисел до 10^8 в консоль займет несколько минут, если не часов.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 01:10     Конкурс(поиск простых чисел) #15
Цитата Сообщение от diagon Посмотреть сообщение
А что говорит?
P.S. если что, у меня вывод идет в файл "output.txt", потому что банально вывод всех простых чисел до 10^8 в консоль займет несколько минут, если не часов.
Тогда может быть и работает. Консоль висит, я и подумал, что не работает. Если 300000, то от 0,1 до 0,15. Если вывод на консоль, то 8.
Цитата Сообщение от diagon Посмотреть сообщение
Если нету gcc, то лучше заменить vector< bool > на vector< int >
Практически ничего не даёт.
Endiff
 Аватар для Endiff
30 / 30 / 1
Регистрация: 19.05.2012
Сообщений: 67
25.07.2012, 03:38     Конкурс(поиск простых чисел) #16
Цитата Сообщение от alsav22 Посмотреть сообщение
То же и у Endiff. 3,1 , но как это читать? Вообще без пробелов. С пробелами - 4,2, с переводом строки 14,8.
Стоп стоп стоп. По-моему, препроцессор удаляет все символы пробела и комментрарии, и коду без разницы, сколько в нем пробелом и комментариев? Не?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 04:09     Конкурс(поиск простых чисел) #17
Цитата Сообщение от Endiff Посмотреть сообщение
Стоп стоп стоп. По-моему, препроцессор удаляет все символы пробела и комментрарии, и коду без разницы, сколько в нем пробелом и комментариев? Не?
Имелось ввиду, что при выводе на консоль нет пробелов между числами.
C++
1
2
3
4
5
cout << 2 <<  3 << 5; 
for (i = 6; i <= limit; i++) {
    if (is_prime[i]){
       cout << i;
    }
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
25.07.2012, 05:47     Конкурс(поиск простых чисел) #18
господа, решето Эратосфена кто-нибудь пробовал на этой задаче?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 10:46     Конкурс(поиск простых чисел) #19
Цитата Сообщение от salam Посмотреть сообщение
господа, решето Эратосфена кто-нибудь пробовал на этой задаче?
У меня оптимизированная реализация:
Во-первых, проверяются только нечетные числа, это снижает время работы и память в 2 раза.
Во-вторых, просеивание идет только до корня из n, это, опять же, значительно увеличивает производительность.
Ну и в третьих, используется vector< bool >, который отлично сочетается с оптимизациями gcc(в данном случае он работает раза в полтора быстрее, чем обычный массив). Ну и еще он уменьшает память в 8 раз.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2012, 16:19     Конкурс(поиск простых чисел)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Small Lamer
 Аватар для Small Lamer
142 / 142 / 48
Регистрация: 05.04.2011
Сообщений: 270
25.07.2012, 16:19     Конкурс(поиск простых чисел) #20
Если кому интересно , http://e-maxx.ru/algo/eratosthenes_sieve
Yandex
Объявления
25.07.2012, 16:19     Конкурс(поиск простых чисел)
Ответ Создать тему
Опции темы

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