Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
1

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

01.01.2013, 15:08. Просмотров 1659. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.01.2013, 15:08
Ответы с готовыми решениями:

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

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

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

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

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

29
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 15:24 2
Очень плохой алгоритм, попробуйте использовать решето Эратосфена(только при таких ограничениях оно пожрет ~250 мбайт) или решето Аткина(тут с памятью уже получше будет, должно уложиться в мегабайт).
И еще, дайте ссылку на тестирующую систему с этой задачей, если такая имеется.
1
soon
01.01.2013, 15:29
  #3

Не по теме:

diagon, это на хабр, я полагаю
http://habrahabr.ru/post/164515/

1
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
01.01.2013, 16:52  [ТС] 4

Не по теме:

Хех, быстро рассекретили...
Почему же только С++? Ужас


Мда, решето Аткина... Хоть намекните, а то в вики примере ничего не пойму.

Добавлено через 43 минуты
Вот вроде что-то такое, но на 2^30 не хватает...
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
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int64_t n, i, j;
int64_t sum=0;
cin >> n;
int64_t *a = new int64_t [n]; // создание массива
for (i = 0; i<n; i++) // и инициализация его всеми единицами
{
 a[i] = 1;
};
for (i = 2; i<n; i++) // цикл прохода по всеми массиву с первого простого числа "2"
{
if (a[i] == 1)
{
for (j = i; j<n; j+=i) // вычеркивание всех чисел кратных данному невычеркнутому
{
 a[j] = 0;
}
 a[i] = 1; // присваивание данному числу значение простого
}
}
int64_t q = 0; // вывод всех простых чисел
for (int64_t i = 2; i<n; i++)
{
if (a[i] == 1)
{
//cout << setw(5) << i << " ";
sum+=i;
 q++;
//if (q % 5 == 0) cout << endl;
}
}
cout<<sum;
delete [] a;
return 0;
}
Добавлено через 36 минут
100000000 делает спокойно, миллиард вызывает ошибку. Почему?
0
Nick Alte
Эксперт С++
1647 / 1019 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
01.01.2013, 17:22 5
Число типа int_64 выедает 8 байтов, миллиард таких чисел - 8 ГБ оперативной памяти.
1
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
01.01.2013, 21:55  [ТС] 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
32
33
34
35
36
37
38
39
40
//@Izobara
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
unsigned long n, i, j;
unsigned long sum=0;
cin >> n;
bool *a = new bool [n]; // создание массива
for (i = 0; i<n; i++) // и инициализация его всеми единицами
{
 a[i] = true;
};
for (i = 2; i<n; i++) // цикл прохода по всеми массиву с первого простого числа "2"
{
if (a[i] == true)
{
for (j = i; j<n; j+=i) // вычеркивание всех чисел кратных данному невычеркнутому
{
 a[j] = false;
}
 a[i] = true; // присваивание данному числу значение простого
}
}
unsigned long q = 0; // вывод всех простых чисел
for (unsigned long i = 2; i<n; i++)
{
if (a[i] == true)
{
//cout << setw(5) << i << " ";
sum+=i;
 //q++;
//if (q % 5 == 0) cout << endl;
}
}
cout<<sum;
//delete [] a;
return 0;
}
у меня на 999999999 за 100 секунд. intel core 2 duo, 2Gb RAM - кто может проверить на intel core-i7, или хотя бы i5?

Добавлено через 1 час 2 минуты
Ну товарищи, проверьте кто-нибудь.

Добавлено через 1 час 37 минут
Хм, нет, 2 минуты - это со сборкой. 69 секунд.
0
HighPredator
5680 / 2002 / 720
Регистрация: 10.12.2010
Сообщений: 5,759
Записей в блоге: 3
01.01.2013, 23:03 7
Если использовать такую реализацию на основе рандомизированного теста простоты Миллера-Рабина, то выйдет примерно 45 минут на моем железе (если вычислять до 230).
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<ctime>
#include<cmath>
 
using namespace std;
 
int ModExp(unsigned int a,unsigned int b,unsigned int n)
{
    unsigned char bits[64];
    unsigned int d=b;   
    unsigned int k=0;
    while(d>0)
    {
        bits[k]=d%2;
        k++;        
        d/=2;
    }
    d=1;
    for(unsigned int i=k-1;i>-1;i--)
    {
        d=(d*d)%n;
        if(bits[i]==1) d=(d*a)%n;
    }
    return d;
}
 
bool Witness(unsigned int a,unsigned int n)
{
    bool flag=false;
    unsigned int t=1;
    unsigned int u=(n-1)/2;
    unsigned int *x;
    unsigned int p=1<<t;
    while(u%2==0)
    {
        u=(n-1)/p;
        t++;
        p=1<<t;     
    }
    x=new unsigned int[t+1];
    x[0]=ModExp(a,u,n);
    unsigned int i=1;
    while((i<=t)&&(flag==false))
    {
        x[i]=(x[i-1]*x[i-1])%n;
        if((x[i]==1)&&(x[i-1]!=1)&&(x[i-1]!=n-1)) flag=true;
        i++;
    }
    if(x[t]!=1) flag=true;
    delete []x;
    return flag;    
}
 
bool Miller_Rabin(unsigned int n,unsigned int s)
{
    for(unsigned int i=0;i<s;i++)
    {
        int a=rand()%(n-1)+1;
        if(Witness(a,n)==true) return false;//составное
    }
    return true;//простое
}
 
bool IsPrime(int d)
{
    bool flag=false;
    if((d>1)&&(d<1000000))
    {
        flag=true;
        int k=floor(sqrt(d*1.0));
        int i=2;
        while((i<=k)&&(flag==true))
        {
            if(d%i==0) flag=false;
            i++;
        }
    }
    else flag=Miller_Rabin(d,5);
    return flag;
}
 
int main()
{
    srand(time(0));
    __int64 sum=0;
    const unsigned int N=1073741824;
    for(unsigned int i=0;i<=N;i++) 
        if(IsPrime(i)==true) sum+=i;        
    cout<<sum<<endl;
    getchar();
    return 0;
}
Результата я не дождался
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 23:12 8
Я тоже поучаствовал.
На моем клэнге в худшем тесте работает за 0.104, однако у меня проц слабый(2х1.6ггц). На i7 должно летать :)
Хотя, можно было бы ускорить мой код еще раза в 3, но мне было лень и я боялся ошибиться(итак набыдлокодил нехило).
Если что, делал через модифицированное решето Эратосфена
0
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
01.01.2013, 23:39  [ТС] 9
Возрадуйтесь, народы! 69 секунд на моем железе! (2х2.2Ггц)
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
//@Izobara
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
 unsigned long long n, i, j;
 unsigned long long sum=0;
cin >> n;
 bool *a = new bool [n]; // создание массива
for (i = 0; i<n; i++) // и инициализация его всеми единицами
{
   a[i] = true;
};
for (i = 2; i<n; i++) // цикл прохода по всеми массиву с первого простого числа "2"
{
  if (a[i] == true)
{
for (j = i; j<n; j+=i) // вычеркивание всех чисел кратных данному невычеркнутому
{
   a[j] = false;
}
   a[i] = true; // присваивание данному числу значение простого
}
}
 for (unsigned long long i = 2; i<n; i++)
{
  if (a[i] == true)
{
 sum+=i;
}
}
cout<<sum;
  delete [] a;
return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
работает за 0.104
0.104 чего? Это в каких единицах? Надеюсь, в секундах
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 23:41 10
Цитата Сообщение от Izobara Посмотреть сообщение
0.104 чего? Это в каких единицах? Надеюсь, в секундах
Ну да.
Слишком строгие там ограничения :( Всего один день и 1024 байт на исходник - это негуманно.
0
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 00:00  [ТС] 11
0.104 секунды? Мой Эратосфен обиделся и меньше, чем на минуту с натяжкой под core i7 не соглашается. 0.104 секунды... У меня 10 в 5 степени будет дольше искать, наверное, рекурсией.

Добавлено через 13 минут
О, конец...
Выложите, пожалуйста, свое решение.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:07 12
Оно сильно обфусцировано(2 строки по 400+ символов), ибо в 1024 байта не укладывался.
Но первая очевидная оптимизация такая - можно разбить весь отрезок [1, 2**30] на n блоков(у меня n = 64), для каждого из них предподсчитать ответ, а потом искать простые числа на отрезке [левая граница блока, входные данные]. Это позволяет сократить перебор в n раз. А дальше нужно просто оптимизировать решето Эратосфена либо другой алгоритм по самые гланды(а оптимизаций для решета крайне много, я вот все, что хотел, просто не успел реализовать).
1
Bringoff
СуперМодулятор
133 / 132 / 48
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 00:11  [ТС] 13
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//@Zver1992
#import<iostream>
#import<algorithm>
#import<cstring>
using namespace std;
#define W(x)  1<<(x&15)
#define E else if
#define C for
#define S 32770
#define B 240240
#define P B/16
#define M 1<<16
#define G(y,x) (y[x>>4]&W(x))
#define D(y,x) (y[x>>4]|=W(x))
#define F(y,x) (y[x>>4]^=W(x))
int s[S],p[S],z[P],b[P],a[M],c[M],i,j,k,n,m=0;int64_t r=0,f=0;
int main() {
cin>>n;C(j=0;j<M;j++)C(i=0;i<16;i++)if((~j>>i)&1) ++c[j],a[j]+=i;C(i=2;i<S;++i)if(!s[i]){p[m++]=i;C(j=i*i;j<S;j+=i)s[j]=1;}C(i=0;i<6;++i)C(j=0;j<B;j+=p[i])D(z,j);k=n/B;
if(k>=3911)r+=0x4dd4a7afd0d425,f=3911*B;E(k>=3747)r+=0x4797565d1da3e6,f=3747*B;E(k>=3353)r+=0x39a5e57663a2a0,f=3353*B;E(k>=2235)r+=0x1a24d4ed4d2249,f=2235*B;E(k>=1118)r+=0x6c82b2b46d0f7,f=1118*B;
C(i=f;i<=n;i+=B){memcpy(b,z,60060);C(j=6;j<m;j++){k=max((i+p[j]-1)/p[j],2)*p[j]-i;C(;k<B;k+=p[j])D(b,k);}if(!i){D(b,1);C(j=0;j<6;j++)F(b,p[j]);}if(i+B>n){r+=(i==0&&n>=2)*2;C(j=1;j<min(B,n-i+1);j+=2)if(!G(b,j))r+=j+i;}else C(j=0,f=i;j<P;j++,f+=16)r+=f*c[b[j]]+a[b[j]];}cout<<r<<endl;}
Надеюсь, это не Ваш код?
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:16 14
Цитата Сообщение от Izobara Посмотреть сообщение
Надеюсь, это не Ваш код?
Нет, не мой.
0
nonedark2008
1051 / 785 / 220
Регистрация: 28.07.2012
Сообщений: 2,191
02.01.2013, 00:37 15
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:44 16
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
Не думаю, что Аткин в этом соревновании победит. Хотя, я плоховато знаю этот алгоритм.
В любом случае, многопоточность не стоит использовать, так как при грамотных решениях потоки дольше создавались бы, чем работали.
0
nonedark2008
1051 / 785 / 220
Регистрация: 28.07.2012
Сообщений: 2,191
02.01.2013, 01:05 17
Цитата Сообщение от diagon Посмотреть сообщение
многопоточность не стоит использовать
Да, все зависит от того, каково будет финальное время, и уже по этому решать помогла бы мультипоточность или нет. Хотя, наверняка те, кто участвовал в ивенте для себя уже все проверили. Так что денек придется подождать до результата.
0
HighPredator
02.01.2013, 01:17
  #18

Не по теме:

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

0
nonedark2008
1051 / 785 / 220
Регистрация: 28.07.2012
Сообщений: 2,191
02.01.2013, 01:36 19
Цитата Сообщение от HighPredator Посмотреть сообщение
Наиболее быстро отработает решето Сундарама.
В конце статьи упоминается, что оно хуже...
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
02.01.2013, 01:37 20
HighPredator, решето Сундарама это только показательный алгоритм, если его так можно назвать.Работает он в разы хуже, чем Аткин или Эратосфен.Или я просто не понял сарказма?
0
02.01.2013, 01:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2013, 01:37

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

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

Олимпиадная задача Сумма простых
наприме мы вводим размер массива 3 потом сколько чисел надо сложить 2 а потом...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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