Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
СуперМодулятор
 Аватар для Bringoff
134 / 134 / 48
Регистрация: 03.11.2012
Сообщений: 974

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

01.01.2013, 15:08. Показов 3410. Ответов 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;
}
В С++ я новичок, поэтому прошу помочь вписаться в рамки
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
01.01.2013, 15:08
Ответы с готовыми решениями:

Сумма квадратов простых чисел
Посчитать сумму квадратов N первых простых чисел, где значение N задает пользователь

Сумма квадратов n первых простых чисел
Рассчитать сумму квадратов n первых простых чисел ,где n вводится с клавиатури. Dev C++/

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

29
02.01.2013, 01:45

Не по теме:

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

0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 19:50
Охщи, первое место.
0
02.01.2013, 20:19

Не по теме:

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

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

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

Не по теме:


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

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

0
02.01.2013, 22:45

Не по теме:

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

1
СуперМодулятор
 Аватар для Bringoff
134 / 134 / 48
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 22:49  [ТС]

Не по теме:


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


А не обфусцированный (фухх, как-то так) код у Вас есть? Интересно...
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 22:52
Есть менее обфусцированный(просто отформатирован код, переименована часть переменных, добавлены комменты).
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);
}
В хабракомментариях мой алгоритм уже разжевали, причем еще до того, как я заметил топик с результатами.
2
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
02.01.2013, 23:16
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 секунд
точнее интересуют сами строки в ковычках.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 23:19
Цитата Сообщение от Kastaneda Посмотреть сообщение
точнее интересуют сами строки в ковычках.
В них лежат зашифрованные ответы для каждого из 64 блоков. Я как бы делю весь входной интервал на 64 блока, и начинаю пилить от левой границы блока, а не с самого начала, т.к. ответ для левой границы у меня уже подсчитан(и вытаскивается из строки).
2
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
03.01.2013, 09:36

Не по теме:

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



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

Не по теме:

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
03.01.2013, 09:36

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

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

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

Из всех пар простых чисел, сумма которых равна заданному числу, найти пару, содержащую наименьшее простое число
Известно, что любое чётное число, большее 2, представимо в виде суммы 2 простых чисел, причём таких разложений может быть несколько. ...

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


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Новые блоги и статьи
[golang] Pipeline
alhaos 08.06.2026
Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .
Свет внутри себя
kumehtar 07.06.2026
Пусть это будет здесь lIs4oanZS9Y
Программа для com-порта
Uhbif79 05.06.2026
Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[
anaschu 01.06.2026
Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .
21 мат мед. Планы на развитие модели здравоСохранения
anaschu 01.06.2026
AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .
20. Мат мед. Абсентеизм как отдельный тип простоя
anaschu 29.05.2026
Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .
19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип
anaschu 28.05.2026
Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта
Eddy_Em 28.05.2026
Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru