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

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

Войти
Регистрация
Восстановить пароль
 
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
#1

По заданному n необходимо вычислить G - C++

23.05.2012, 19:41. Просмотров 337. Ответов 0
Метки нет (Все метки)

...Может показаться простым. По заданному n необходимо вычислить G. Значение G вычисляется следующим образом:
Через GCD(i, j) обозначено наибольший общий делитель целых чисел i и j.
C++
1
2
3
4
5
6
G = 0;
for(i = 1; i < n; i++)
for(j = i + 1;j <= n; j++)
{
    G += GCD(i,j);
}
/*Функция GCD() вычисляет наибольший общий делитель двух чисел*/
Я решил его так:
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
#include <stdio.h>
long gcd( int a, int b )
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}
void recurs()
{   
    __int64 G;
    long n;
        scanf("%ld",&n);
        if (n!=0)
        {
        G=0;
        for(int i=1; i < n;i++)
            for(int j=i+1;j<=n;j++)
                 G+=gcd(i,j);
        printf("%lld\n",G);
        recurs();
        }
}
int main()
{
    recurs();       
}
Но всё выполняется до 3000. потом - не работает. Надо 5 минут ждать для 20000. А мне нужно вычислять до 5000000. Помогите!
пояснение к коду:
Состоит из не более чем 100 строк. Каждая строка содержит целое число n (1 < n < 4000001). Значение n описано выше в условии задачи. Последняя строка содержит n = 0 и не обрабатывается.
Короче по коду будет видно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2012, 19:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По заданному n необходимо вычислить G (C++):

Вычисление степени, в которую необходимо возвести 2 для получения числа, которое <= заданному числу - C++
Помогите написать программу, которая вычисляет целую степень, в которую необходимо возвести число 2, чтобы получить число, ближайшее...

Необходимо определить, есть ли в указанной строке хотя бы один элемент, равный заданному числу - C++
Дан двумерный массив n×m элементов, заполненный целыми числами. Также заданы число a и номер строки i. Необходимо определить, есть ли в...

По заданному X рекурсивно вычислить X^2 - C++
Написать программу, высчитывающую X^2. Х задается пользователем. Использовать рекурсию.

. По заданному вещественному х вычислить значение - C++
По заданному вещественному х вычислить значение

По заданному вещественному x вычислить значение - C++
помогите решить задачу .Позаданному вещественному x вычислить.значение \sqrt{x} по следующей итерационной формуле: ...

Вычислить значение k удовлетворяющее заданному условию - C++
Рассчитать значения функции y=k/(x^k)+(y^k-1) для k=1,2,... . Расчет проводить до тех пор, пока y&gt;=z . Начальные данные x,y и z; (x,y&gt;1)...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2012, 19:41
Привет! Вот еще темы с ответами:

Вычислить значение функции по заданному алгоритму - C++
Доброго времени суток, уважаемые Форумчане! Вынуждена просить Вашей помощи в решении нескольких задач, так как сама на данный момент не...

Вычислить матрицу D по заданному в варианте матричному выражению - C++
Заданы матрицы А, В, С максимальной размерности (20, 20). Вычислить матрицу D по заданному в варианте матричному выражению. Предусмотреть...

Вычислить количество элементов, принадлежащих заданному интервалу - C++
1. Задан массив U(K). Вычислить количество элементов, принадлежащих интервалу , и определить, сколько в нем пар одинаковых соседних...

Вычислить первоначальное число, измененное по заданному алгоритму - C++
В трехзначном числе x зачеркнули его последнюю цифру. Когда в оставшемся двузначном числе переставили цифры, а затем приписали к ним...


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

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

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