Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

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

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

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

24.07.2012, 20:30. Просмотров 6499. Ответов 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) целых положительных чисел. Программа должна найти и выдать в виде списка все...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.07.2012, 20:34 #2
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.
Эм, это ее надо максимально затормаживать что ли?
От 1 до 10^8 можно за секунду найти(если использовать реализацию одного из авторов решета Аткина).
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
24.07.2012, 20:37  [ТС] #3
Нет, я имел ввиду, что программа должна работать за 6 секунд и менее.Вы так думаете, что найти это очень быстро, вы код напишите и проверьте)
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
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;
}
0
dimcoder
Полярный
462 / 434 / 68
Регистрация: 11.09.2011
Сообщений: 1,132
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
0
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 секунд
0
Endiff
31 / 31 / 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;
    }
}
}

Не по теме:

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

0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
24.07.2012, 21:00 #8
diagon вспомнил
0
Endiff
31 / 31 / 1
Регистрация: 19.05.2012
Сообщений: 67
24.07.2012, 21:01 #9
Цитата Сообщение от neske Посмотреть сообщение
diagon вспомнил
Уже увидел, простите
0
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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;
}
1
alsav22
5419 / 4815 / 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.
0
diagon
Higher
1929 / 1195 / 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гц каждый ).
Можно еще многопоточность прикрутить, но мне лень =\
1
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
25.07.2012, 00:42 #13
diagon, что-то этот код не хочет работать.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 00:47 #14
Цитата Сообщение от alsav22 Посмотреть сообщение
diagon, что-то этот код не хочет работать.
А что говорит?
P.S. если что, у меня вывод идет в файл "output.txt", потому что банально вывод всех простых чисел до 10^8 в консоль займет несколько минут, если не часов.
0
alsav22
5419 / 4815 / 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 >
Практически ничего не даёт.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2012, 01:10
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.07.2012, 01:10
Ответ Создать тему
Опции темы

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