Никак не удаётся написать следующюю программу: Дано натуральное число n, выяснить можно ли его представить в виде суммы 4-х простых чисел и вывести все возможные варианты. Буду благодарен, если чем-то поможите.

Цитата(kostyantmb @ 1.12.2004, 00:59)

Дано натуральное число n

Самое большое число какое может быть?

Цитата(kostyantmb @ 1.12.2004, 00:59)

выяснить можно ли его представить в виде суммы 4-х простых чисел и вывести все возможные варианты

Если известно максимальное значение n, то самое простое это сделать массив простых чисел в интервале 0 < X < n-1 где X простое число
методом описаным здесь: http://www.ipkro.isu.ru/informat/olimps/95...od/solut2_2.htm
и реализованным на VB здесь: http://forum.vingrad.ru/index.php?showtopic=30076
и перебрать всевозможные варианты.

Спасибо, может ещё кто-нибудь чего-нибудь подкинет стоющего?
А про n ничего не сказано.

Это сообщение отредактировал(а) kostyantmb - 1.12.2004, 10:08

Если n неизвестно, тогда находить все простые числа от 2-ух до n пользуясь решетом эратосфена : http://alglib.manual.ru/numbers/erat.php
А вообще это надо было постить в алгоритмы

Попробуй

Код

#include <iostream> using namespace std; // int in=0; //Переменная для ввода int* mas; //Массив для записи простых чисел int temp=0; //"Текущий" элемент вышеописанного массива void simple()//Функция записи всех простых чисел меньше in в массив mas { bool prov; for (int x=2; x<in; x++) {  prov=0;  for (int y=2; y<x; y++)   if (x%y==0) prov=1;  if (prov==0)  {   mas[temp]=x;   temp++;  } } } // void out()//Функция вывода на экран содержимого массива { for (int x=0; x<temp; x++)  cout<<mas[x]<<endl; } // void main() { int kol=0; cout<<"int\n->"; cin>>in; mas=new int[in]; simple(); out(); cout<<"_____________________\n"; for (int x=0; x<temp-2; x++)  for (int y=x; y<temp-1; y++)   for (int z=y; z<temp; z++)    if ((mas[x]+mas[y]+mas[z])==in)    {     kol++;     cout<<mas[x]<<"\t"<<mas[y]<<"\t"<<mas[z]<<endl;    } cout<<"_____________________\n"; cout<<"Vsego - "<<kol; delete [] mas; cin.get(); cin.get(); }

Цитата(3)

Если n неизвестно, тогда находить все простые числа от 2-ух до n пользуясь решетом эратосфена

красиво сказал
3,14, а ты смотрел те ссылки, которые я дал?
Alexandr87, а твой вариант чем лучше "решета эратосфена"?

Цитата(kostyantmb @ 1.12.2004, 09:07)

Спасибо, может ещё кто-нибудь чего-нибудь подкинет стоющего?

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

О кстати идея
У тебя число есть, которое нужну из суммы 4 простых чисел слепить. Ну так бери его за n (максимальное простое число) и дело сделано... Можно и еще кое что сделать, но это головная боль, но зато с большими n быстрее работать будет. Если хочешь напишу мыслю...
Добавлено @ 18:37
3,14, кстати алгоритмы по той ссылке, что ты дал ИМХО через одно место сделаны на всех там указанных языках... Я был в шоке

Помоему те, кто их писал вообще слова "оптимизация" не знают...

cardinal

А кто говорит, что он лучше, мне так удобнее.
Кстати сорри, ятам немного недочитал. Я сделал из трех простых чисел, но там немного изменить надо. Но там сложностей не будет нужно еще один цикл for добавить

Там ведь для 4 чисел, где цикл добавить?
и что такое #include <iostream>, может так: #include <iostream.h>???

Код

...... for (int x=0; x<temp-3; x++) for (int y=x; y<temp-2; y++)  for (int z=y; z<temp-1; z++)    for (int c=z; c<temp; c++)    if ((mas[x]+mas[y]+mas[z]+mac[c])==in) ....

#include <iostream> - новый стандарт

У меня Borland C++ его не понимает, как быть в таком случае, может просто использовать stdio.h ? Да, и если можешь выложи, пожалуйста, полный исходник программы, заранее благодарен.

Это сообщение отредактировал(а) kostyantmb - 3.12.2004, 18:29

Прогнал твой исходник, что получил:

1. Ввел число 21.
2. Получил на экране:

->21

2
3
5
7
11
13
17
19
------------------------------------------------------------
2 2 17
2 2 17
3 5 13
3 5 13
3 5 13
3 7 11
3 7 11
3 7 11
3 7 11
5 5 11
5 5 11
5 5 11
5 5 11
7 7 7
7 7 7
7 7 7
7 7 7
-------------------------------------------------------------
vsego - 18

// надо с помощью суммы четырёх чисел.
// да, и ещё вопрос, можно ли решить поставленную задачу без использования массивов.
Добавлено @ 20:04
Вот исходник, который я прогонял:
#include <iostream.h>

int in=0; //Переменная для ввода
int* mas; //Массив для записи простых чисел
int temp=0; //"Текущий" элемент вышеописанного массива

void simple()//Функция записи всех простых чисел меньше in в массив mas
{
for (int x=2; x<in; x++)
{
int prov;
prov=0;
for (int y=2; y<x; y++)
if (x%y==0) prov=1;
if (prov==0)
{
mas[temp]=x;
temp++;
}
}
}
//
void out()//Функция вывода на экран содержимого массива
{
for (int x=0; x<temp; x++)
cout<<mas[x]<<endl;
}
//
void main()
{
int kol=0;
cout<<"int\n->";
cin>>in;
mas=new int[in];
simple();
out();
cout<<"_____________________\n";
for (int x=0; x<temp-3; x++)
for (int y=x; y<temp-2; y++)
for (int z=y; z<temp-1; z++)
for (int c=z; c<temp; c++)
if ((mas[x]+mas[y]+mas[z])==in)
{
kol++;
cout<<mas[x]<<"\t"<<mas[y]<<"\t"<<mas[z]<<endl;
}
cout<<"_____________________\n";
cout<<"Vsego - "<<kol;

delete [] mas;
cin.get();
cin.get();
}

kostyantmb, читай внимательнее, что тебе пишут!
if ((mas[x]+mas[y]+mas[z])==in)

Цитата(cardinal @ 1.12.2004, 15:32)

3,14, кстати алгоритмы по той ссылке, что ты дал ИМХО через одно место сделаны на всех там указанных языках... Я был в шоке Помоему те, кто их писал вообще слова "оптимизация" не знают...

Нда? А ты думаешь они такой сложный код всместо просто двойного цикла по дурости написали?

Цитата(Fantasist @ 3.12.2004, 22:11)

А ты думаешь они такой сложный код всместо просто двойного цикла по дурости написали?

По чисто математическому подходу, а не по подходу с точки зрения эффективного программирования. Это мое предположение. То, что реализовано на VB это то, что придумали Греки и придумали не по дурости Реализовано это на VB ИМХО очень неплохо и без излишеств.

Fantasist, а ты думаешь тот двойной цикл работает медленнее в данном случае, чем вот эта страшилка?

Код

do    {        p(i) = 0;        i = i+1;    }    while(i<=r);    j = 3;    k = 3;    do    {        i = 2;        s = sqrt(k);        c = true;        do        {            i = i+1;            if( p(i)>s )            {                p(j) = k;                j = j+1;                c = false;            }        }        while(ap::trunc(double(k)/double(p(i)))*p(i)!=k&&c);        k = k+2;    }    while(k<=n);

Может конечно Fantasist ты и прав, но чтобы поверить в это надо сделать проверку profiler'ом или вникнуться сильно в алгоритм (что возможно ничего не даст, потому, что теория может оказаться далеко от практики), чего я не делал...

Но даже если по алгоритму получается, что в среднем проходов будет меньше, то это еще ничего не значит. Заключение я (см. выше) сделал исходя из того, что если встречаются каждые столько-то шагов sqrt, деление, умножение и т.д., то вся польза от умного алгоритма пропадает и соответственно простой двойной цикл будет работать быстрее.

Спорить тут нечего. Подход довольно простой. Берется один вариант и второй и проверяется profiler'ом... Если я не прав, то ... то я не прав

2 ALL:
Товарисчи, а как написать эту прогу без использования массивов??? Кстати, условия в первом посте.