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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.81
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

Простые делители - C++

23.04.2009, 22:27. Просмотров 3320. Ответов 25
Метки нет (Все метки)

Требуется написать программу которая находит сумму простых делителей числа n
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
23.04.2009, 22:39     Простые делители #2
Не проверял на работоспособность
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int summ(int n)
{
   int result=1,i=3;
   while(n&1)
   {
      result+=2;
      n/=2;
   }
   while(n!=1)
   {
       while(n%i)i+=2;
       n/=i;
      result+=i;
   }
return result;
}
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
23.04.2009, 22:44  [ТС]     Простые делители #3
Humanitis,
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
#include <stdio.h>
#include <string.h>
#include <ctype.h>
__int64 summ(__int64 n)
{
   __int64 result=1,i;
   while(n&1)
   {
      result+=2;
      n/=2;
   }
   i=3;
   while(n!=1)
   {
       while(n%i)i+=2;
       n/=i;
      result+=i;
   }
return result;
}
main()
{
        __int64 i,x;
        scanf ("%I64d",&i);
        x=summ(i);
        printf ("%I64d",x);
        getchar();
        getchar();
        return 0;
}
вооще, виснет..
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
23.04.2009, 22:48     Простые делители #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int summ(int n)
{
   int result=1,i=3;
   while(!(n&1))//тут поправь
   {
      result+=2;
      n/=2;
   }
   while(n!=1)
   {
       while(n%i)i+=2;
       n/=i;
      result+=i;
   }
return result;
}

З.ы. Отладчиком пользоваться надо учиться
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
23.04.2009, 23:04  [ТС]     Простые делители #5
Цитата Сообщение от Humanitis Посмотреть сообщение
З.ы. Отладчиком пользоваться надо учиться
А что это вооще???

Добавлено через 5 минут 6 секунд
Цитата Сообщение от Humanitis Посмотреть сообщение
C++
1
2
3
int summ(int n)
{
   int result=1,i=3;

З.ы. Отладчиком пользоваться надо учиться

Неполное решение неверный ответ выдает, мне надо бы чтобы для 10^9 степени работало но по моему время подожмет потому что надо за 2 сек

Добавлено через 9 минут 48 секунд
Humanitis, ты тут"???
Monte-Cristo
2786 / 1372 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
23.04.2009, 23:25     Простые делители #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
#include <iostream>
using namespace std;
 
int summ(int n)
{
    int sum = 0;
    for (int i=1; i<=n; i++)
    {
        if (n%i == 0)
        {
            int kol = 0;
            for (int j=2; j<i; j++)
                if (i%j == 0) kol++;
            if (kol == 0) sum += i;
        }
    }
    return sum;
}
 
int main()
{
    int n;
    cout << "Enter integer: ";
    cin >> n;
 
    cout << "\nResult: " << summ(n) << endl;
    return 0;
}
Evg
Эксперт CАвтор FAQ
17275 / 5529 / 345
Регистрация: 30.03.2009
Сообщений: 15,041
Записей в блоге: 26
23.04.2009, 23:44     Простые делители #7
Monte-Cristo, у тебя квадратичный алгоритм. Исходя из поста #5 надо чтобы по времени быстро работало. Алгоритм Humanitis'а, похоже, этим свойством обладает, т.к. с такими делениями циклы получаются короткие. Правда матчасть этого алгоритма я не понимаю
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:38     Простые делители #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int summ(int n)
{
   int result=1,i=3;//result=1 считаем,что единица тоже простой делитель,i=3 первый простой делитель след. за 2
   while(!(n&1))//пока делится на 2
   {
      result+=2;//увеличиваем сумму делителей на 2
      n/=2;
   }
   while(n!=1)
   {
       while(n%i)i+=2;//пока i не делитель n увеличиваем его на 2,берем все нечетные числа(единственный четный делитель 2 мы уже проверили выше)
       n/=i;//исключаем найденный нами делитель из нашего числа
      result+=i;//увеличиваем результат на этот делитель
   }
return result;
}
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:40  [ТС]     Простые делители #9
Humanitis, Это я понял... Но вот задачка мне нужна для чисел 10^9 степени....
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:56     Простые делители #10
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:58  [ТС]     Простые делители #11
Цитата Сообщение от Humanitis Посмотреть сообщение
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
проблемка в том что проверяющая системка __int64 не берет
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 09:01     Простые делители #12
unsigned long
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:12  [ТС]     Простые делители #13
Там из 65 тестов прошло 47, 17 неправильных ответов, 1 TLE time limit
Evg
Эксперт CАвтор FAQ
17275 / 5529 / 345
Регистрация: 30.03.2009
Сообщений: 15,041
Записей в блоге: 26
24.04.2009, 09:19     Простые делители #14
Цитата Сообщение от Humanitis Посмотреть сообщение
unsigned long
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:51  [ТС]     Простые делители #15
Цитата Сообщение от Evg Посмотреть сообщение
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
и так тож не получается
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:03     Простые делители #16
Evg, Да даже 32 битный вмещает 10^9.
Новенький, Могу только посоветовать перед считыванием данных сгенирировать массив простых чисел от 3 до sqrt(10^9). потом просто в качестве делителей брать числа из этого массива. Так будет быстрее
Evg
Эксперт CАвтор FAQ
17275 / 5529 / 345
Регистрация: 30.03.2009
Сообщений: 15,041
Записей в блоге: 26
24.04.2009, 10:07     Простые делители #17
Цитата Сообщение от Humanitis Посмотреть сообщение
Evg, Да даже 32 битный вмещает 10^9.
Изначальная постановка вопроса была "проблемка в том что проверяющая системка __int64 не берет", на что ты посоветовал использовать long. Я и возразил, что для 64-битного числа нужен long long. Лишь после твоего комментария я понял, что ты НЕ предлагал использовать long в качестве 64-битного значения, а просто попросил поменять __int64 на long, чтобы задача скомпилировалась.
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:17     Простые делители #18
Новенький,
Попробуй еще это вставить
C++
1
2
3
4
5
6
7
8
9
#if UINT_MAX>=1000000000
#define UINT unsigned int
#else
#if ULONG_MAX>=1000000000 
#define UINT unsigned long int
#else
#define UINT unsigned long long int
#endif
#endif
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 10:19  [ТС]     Простые делители #19
где вставить???
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
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
using namespace std;
unsigned long long summ(unsigned long long n)
{
   unsigned long long result=0,i;
   while(!(n&1))
   {
      result+=2;
      n/=2;
   }
   i=3;
   while(n!=1)
   {
       while(n%i)i+=2;
       n/=i;
      result+=i;
   }
return result;
}
main()
{
        unsigned long long i,x;
        cin>>i;
        x=summ(i);
        cout<<x;
        getchar();
        getchar();
        return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2009, 10:22     Простые делители
Еще ссылки по теме:

Получить все простые делители заданного числа C++
Получить все простые делители натурального числа C++
C++ Найти все простые делители заданного натурального числа
Получить все простые делители заданного натурального числа C++
Получить все простые делители числа C++

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

Или воспользуйтесь поиском по форуму:
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:22     Простые делители #20
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
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <limits.h>
#include <stddef.h>
#if UINT_MAX>=1000000000
#define UINT unsigned int
#else
#if ULONG_MAX>=1000000000 
#define UINT unsigned long int
#else
#define UINT unsigned long long int
#endif
#endif
using namespace std;
UINT summ(UINT n)
{
   UINT result=0,i;
   while(!(n&1))
   {
      result+=2;
      n/=2;
   }
   i=3;
   while(n!=1)
   {
       while(n%i)i+=2;
       n/=i;
      result+=i;
   }
return result;
}
main()
{
        UINT i,x;
        cin>>i;
        x=summ(i);
        cout<<x;
        getchar();
        getchar();
        return 0;
}
Yandex
Объявления
24.04.2009, 10:22     Простые делители
Ответ Создать тему
Опции темы

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