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

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

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

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

01.01.2013, 15:08. Просмотров 1490. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сумма простых чисел ускорение (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...

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

Добавлено через 13 минут
О, конец...
Выложите, пожалуйста, свое решение.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:07 #12
Оно сильно обфусцировано(2 строки по 400+ символов), ибо в 1024 байта не укладывался.
Но первая очевидная оптимизация такая - можно разбить весь отрезок [1, 2**30] на n блоков(у меня n = 64), для каждого из них предподсчитать ответ, а потом искать простые числа на отрезке [левая граница блока, входные данные]. Это позволяет сократить перебор в n раз. А дальше нужно просто оптимизировать решето Эратосфена либо другой алгоритм по самые гланды(а оптимизаций для решета крайне много, я вот все, что хотел, просто не успел реализовать).
1
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;}
Надеюсь, это не Ваш код?
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.01.2013, 00:16 #14
Цитата Сообщение от Izobara Посмотреть сообщение
Надеюсь, это не Ваш код?
Нет, не мой.
0
nonedark2008
925 / 664 / 142
Регистрация: 28.07.2012
Сообщений: 1,809
02.01.2013, 00:37 #15
Думаю, что лучший результат будет у того, кто сделает решето Аткина + добавит мультипоточность. А то примеры выкладывали, но про потоки что-то никто не вспомнил...
Будет интересно увидеть финальный результат.
0
02.01.2013, 00:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2013, 00:37
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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