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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
01.01.2013, 15:08     Сумма простых чисел ускорение #1
Надо находить сумму всех простых чисел. Ограничения: на числе прибл. 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     Сумма простых чисел ускорение
Посмотрите здесь:

массив целых чисел состоит из n элементов, найти сумму простых чисел, входящих в него C++
C++ Дана последовательность целых чисел а1, а2, …, an. Выяснить, является ли она симметричной последовательностью простых чисел
Последовательность чисел, определить среднее арифметическое простых чисел C++
C++ Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?
C++ Найти максимальное число которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
02.01.2013, 01:45     Сумма простых чисел ускорение
  #21

Не по теме:

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 19:50     Сумма простых чисел ускорение #22
Охщи, первое место.
soon
02.01.2013, 20:19
  #23

Не по теме:

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

Bringoff
СуперМодулятор
 Аватар для 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
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 22:49  [ТС]     Сумма простых чисел ускорение #26

Не по теме:


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


А не обфусцированный (фухх, как-то так) код у Вас есть? Интересно...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 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
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 23:19     Сумма простых чисел ускорение #29
Цитата Сообщение от Kastaneda Посмотреть сообщение
точнее интересуют сами строки в ковычках.
В них лежат зашифрованные ответы для каждого из 64 блоков. Я как бы делю весь входной интервал на 64 блока, и начинаю пилить от левой границы блока, а не с самого начала, т.к. ответ для левой границы у меня уже подсчитан(и вытаскивается из строки).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.01.2013, 09:36     Сумма простых чисел ускорение
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
03.01.2013, 09:36     Сумма простых чисел ускорение #30

Не по теме:

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



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

Не по теме:

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

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

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