Форум программистов, компьютерный форум 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 простых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 15:24     Сумма простых чисел ускорение #2
Очень плохой алгоритм, попробуйте использовать решето Эратосфена(только при таких ограничениях оно пожрет ~250 мбайт) или решето Аткина(тут с памятью уже получше будет, должно уложиться в мегабайт).
И еще, дайте ссылку на тестирующую систему с этой задачей, если такая имеется.
soon
01.01.2013, 15:29
  #3

Не по теме:

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

Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 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 делает спокойно, миллиард вызывает ошибку. Почему?
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
01.01.2013, 17:22     Сумма простых чисел ускорение #5
Число типа int_64 выедает 8 байтов, миллиард таких чисел - 8 ГБ оперативной памяти.
Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 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 секунд.
HighPredator
 Аватар для HighPredator
5351 / 1734 / 320
Регистрация: 10.12.2010
Сообщений: 5,120
Записей в блоге: 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;
}
Результата я не дождался
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 23:12     Сумма простых чисел ускорение #8
Я тоже поучаствовал.
На моем клэнге в худшем тесте работает за 0.104, однако у меня проц слабый(2х1.6ггц). На i7 должно летать :)
Хотя, можно было бы ускорить мой код еще раза в 3, но мне было лень и я боялся ошибиться(итак набыдлокодил нехило).
Если что, делал через модифицированное решето Эратосфена
Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 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 чего? Это в каких единицах? Надеюсь, в секундах
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.01.2013, 23:41     Сумма простых чисел ускорение #10
Цитата Сообщение от Izobara Посмотреть сообщение
0.104 чего? Это в каких единицах? Надеюсь, в секундах
Ну да.
Слишком строгие там ограничения :( Всего один день и 1024 байт на исходник - это негуманно.
Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
02.01.2013, 00:00  [ТС]     Сумма простых чисел ускорение #11
0.104 секунды? Мой Эратосфен обиделся и меньше, чем на минуту с натяжкой под core i7 не соглашается. 0.104 секунды... У меня 10 в 5 степени будет дольше искать, наверное, рекурсией.

Добавлено через 13 минут
О, конец...
Выложите, пожалуйста, свое решение.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:07     Сумма простых чисел ускорение #12
Оно сильно обфусцировано(2 строки по 400+ символов), ибо в 1024 байта не укладывался.
Но первая очевидная оптимизация такая - можно разбить весь отрезок [1, 2**30] на n блоков(у меня n = 64), для каждого из них предподсчитать ответ, а потом искать простые числа на отрезке [левая граница блока, входные данные]. Это позволяет сократить перебор в n раз. А дальше нужно просто оптимизировать решето Эратосфена либо другой алгоритм по самые гланды(а оптимизаций для решета крайне много, я вот все, что хотел, просто не успел реализовать).
Bringoff
СуперМодулятор
 Аватар для Bringoff
132 / 131 / 15
Регистрация: 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;}
Надеюсь, это не Ваш код?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:16     Сумма простых чисел ускорение #14
Цитата Сообщение от Izobara Посмотреть сообщение
Надеюсь, это не Ваш код?
Нет, не мой.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
02.01.2013, 00:37     Сумма простых чисел ускорение #15
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:44     Сумма простых чисел ускорение #16
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
Не думаю, что Аткин в этом соревновании победит. Хотя, я плоховато знаю этот алгоритм.
В любом случае, многопоточность не стоит использовать, так как при грамотных решениях потоки дольше создавались бы, чем работали.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
02.01.2013, 01:05     Сумма простых чисел ускорение #17
Цитата Сообщение от diagon Посмотреть сообщение
многопоточность не стоит использовать
Да, все зависит от того, каково будет финальное время, и уже по этому решать помогла бы мультипоточность или нет. Хотя, наверняка те, кто участвовал в ивенте для себя уже все проверили. Так что денек придется подождать до результата.
HighPredator
02.01.2013, 01:17
  #18

Не по теме:

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

nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
02.01.2013, 01:36     Сумма простых чисел ускорение #19
Цитата Сообщение от HighPredator Посмотреть сообщение
Наиболее быстро отработает решето Сундарама.
В конце статьи упоминается, что оно хуже...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2013, 01:37     Сумма простых чисел ускорение
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
02.01.2013, 01:37     Сумма простых чисел ускорение #20
HighPredator, решето Сундарама это только показательный алгоритм, если его так можно назвать.Работает он в разы хуже, чем Аткин или Эратосфен.Или я просто не понял сарказма?
Yandex
Объявления
02.01.2013, 01:37     Сумма простых чисел ускорение
Ответ Создать тему
Опции темы

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