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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
#1

Сумма простых чисел ускорение - C++

01.01.2013, 15:08. Просмотров 1443. Ответов 29
Метки нет (Все метки)

Надо находить сумму всех простых чисел. Ограничения: на числе прибл. 1000000000 надо вписаться в минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
 
 
int main() {
    std::vector<int> vec(1, 2);
    int64_t i,TOP,sum=0;
    std::cin>>TOP;
    for ( int current = 3; current <= TOP; current += 2 ) {
        for ( i = 1; i < vec.size(); ++i )
            if ( ! ( current % vec[i] ) )
                break;
        if ( i == vec.size() )
            vec.push_back(current);
    }
 
    for ( i = 0; i < vec.size(); ++i )
     
        sum+=vec[i];
 
    std::cout <<sum;
    return 0;
}
В С++ я новичок, поэтому прошу помочь вписаться в рамки
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.01.2013, 15:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сумма простых чисел ускорение (C++):

Найти количество простых чисел, сумма цифр которых равна натуральному числу - C++
В одномерном массиве, состоящем из N натуральных чисел найти количество простых чисел, сумма цифр которых равна заданному натуральному...

Найти n первых простых чисел, сумма цифр у которых меньше заданного числа - C++
Помогите написать программу! Условие: найти n первых простых чисел, сумма цифр у которых меньше заданного m.

Найти максимальное число которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел - C++
Найти максимальное число, меньшее заданного, которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел (минимальное такое...

Найти среди простых чисел, попадающих в этот промежуток, такое число, у которого сумма цифр максимальная - C++
1.В функцию передаются границы числового интревала. Найти среди простых чисел, попадающих в этот промежуток, такое число, у которого сумма...

Сумма простых. Где ошибка? - C++
Найти сумму только тех элементов числовой последовательности, значения которых являются простыми числами. Входные данные: Во входном...

Олимпиадная задача Сумма простых - C++
наприме мы вводим размер массива 3 потом сколько чисел надо сложить 2 а потом массив 6 5 7 и вы водитьса другой массив например 6+5=11...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:44 #16
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
Не думаю, что Аткин в этом соревновании победит. Хотя, я плоховато знаю этот алгоритм.
В любом случае, многопоточность не стоит использовать, так как при грамотных решениях потоки дольше создавались бы, чем работали.
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
02.01.2013, 01:05 #17
Цитата Сообщение от diagon Посмотреть сообщение
многопоточность не стоит использовать
Да, все зависит от того, каково будет финальное время, и уже по этому решать помогла бы мультипоточность или нет. Хотя, наверняка те, кто участвовал в ивенте для себя уже все проверили. Так что денек придется подождать до результата.
HighPredator
02.01.2013, 01:17
  #18

Не по теме:

Наиболее быстро отработает решето Сундарама. Теория говорит, что он в 3-4 раза быстрее.

nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
02.01.2013, 01:36 #19
Цитата Сообщение от HighPredator Посмотреть сообщение
Наиболее быстро отработает решето Сундарама.
В конце статьи упоминается, что оно хуже...
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
02.01.2013, 01:37 #20
HighPredator, решето Сундарама это только показательный алгоритм, если его так можно назвать.Работает он в разы хуже, чем Аткин или Эратосфен.Или я просто не понял сарказма?
HighPredator
02.01.2013, 01:45
  #21

Не по теме:

Это был очень хитрый сарказм

diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 19:50 #22
Охщи, первое место.
soon
02.01.2013, 20:19
  #23

Не по теме:

diagon, поздравляю! Отличный код!

Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 22:38  [ТС] #24
Я почему-то сразу понял, что это Вы.

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

Не по теме:


Мда, опять я без инвайта. 4 поста в песочницу не пустили.

А почему у Вас разные ники тут и ?

diagon
02.01.2013, 22:45
  #25

Не по теме:

Цитата Сообщение от Izobara Посмотреть сообщение
А почему у Вас разные ники тут и ?
Здесь мой старый ник. Я в один прекрасный день узнал, что у этого ника есть перевод, который мне не понравился. С тех пор у меня другой ник.

Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 22:49  [ТС] #26

Не по теме:


Так поменяйте ник. Один раз можно!


А не обфусцированный (фухх, как-то так) код у Вас есть? Интересно...
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 22:52 #27
Есть менее обфусцированный(просто отформатирован код, переименована часть переменных, добавлены комменты).
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
52
53
54
55
56
//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
 
unsigned  i, n, sq, j, left;
long long u[66], answer;
 
int main()
{
    //расшифровка предподсчета
    for ( ; i < 64 * 7; i++)
    {
        u[i / 7 + 2] = u[i / 7 + 2] * 96 + "+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
            "5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i] - 32;
    }
    for (i = 0; i < 64; i++)
    {
        u[i + 2] += 2 * u[i + 1] - u[i];
    }
 
    scanf("%u", &n);
    sq = sqrt(n) + 1e-7;
    left = n >> 24 << 24;
    answer = u[(n >> 24) + 1] + 2 * !left * (n > 1);
 
    std::vector<bool> sieve(sq / 2 + 1), B(n - left + 2);
    B[1] = !left;
 
    //блочное решето
    for (i = 3; i <= sq; i += 2)
    {
        if (!sieve[i / 2])
        {
            //просеивание до корня
            for (j = 3 * i; j <= sq; j += 2 * i)
            {
                sieve[j / 2] = 1;
            }
 
            //просеивание блока
            for (j = left ? (left + i - 1) / i * i : 2 * i; j <= n; j += i)
            {
                B[j - left] = 1;
            }
        }
    }
 
    //подсчет ответа
    for (i = 1; i + left <= n; i += 2)
    {
        B[i] ? 0 : answer += i + left;
    }
 
    printf("%llu\n", answer);
}
В хабракомментариях мой алгоритм уже разжевали, причем еще до того, как я заметил топик с результатами.
Kastaneda
Форумчанин
Эксперт С++
4652 / 2860 / 228
Регистрация: 12.12.2009
Сообщений: 7,268
Записей в блоге: 2
Завершенные тесты: 1
02.01.2013, 23:16 #28
diagon, что-то после праздников не могу понять сакральную роль строк
C++
1
2
u[i / 7 + 2] = u[i / 7 + 2] * 96 + "+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
            "5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i] - 32;
может объяснишь?

Добавлено через 35 секунд
точнее интересуют сами строки в ковычках.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 23:19 #29
Цитата Сообщение от Kastaneda Посмотреть сообщение
точнее интересуют сами строки в ковычках.
В них лежат зашифрованные ответы для каждого из 64 блоков. Я как бы делю весь входной интервал на 64 блока, и начинаю пилить от левой границы блока, а не с самого начала, т.к. ответ для левой границы у меня уже подсчитан(и вытаскивается из строки).
Kastaneda
Форумчанин
Эксперт С++
4652 / 2860 / 228
Регистрация: 12.12.2009
Сообщений: 7,268
Записей в блоге: 2
Завершенные тесты: 1
03.01.2013, 09:36 #30

Не по теме:

Цитата Сообщение от diagon Посмотреть сообщение
В них лежат зашифрованные ответы для каждого из 64 блоков.
Ну это понятно, что там что-то зашифрованное Вопрос был немного в другом - как ты const char* в арифметике используешь. Но сейчас я уже заметил, что там в конце подписано [i], поэтому вопрос снимаю, а вчера я этого не видел, и был очень удивлен как оно вообще компилится



Добавлено через 37 секунд

Не по теме:

а и поздравляю с победой!

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.01.2013, 09:36
Привет! Вот еще темы с ответами:

Вычислить количество простых чисел среди положительных чисел массива - C++
Дан массив целых положительных и отрицательных чисел в количестве меньше или равно 64 . А требуется , Вычислить количество простых чисел...

Дан массив целых чисел. Верно ли, что он состоит только из простых чисел? - C++
Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?

Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел последовательности - C++
Использовать функции в программе Задание: Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел...

Массив целых чисел состоит из n элементов, найти сумму простых чисел, входящих в него - C++
массив целых чисел состоит из n элементов, найти сумму простых чисел, входящих в него.


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

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

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