Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.81
Новенький
44 / 9 / 3
Регистрация: 03.03.2009
Сообщений: 254
#1

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

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

Требуется написать программу которая находит сумму простых делителей числа n
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2009, 22:27
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Простые делители (C++):

Взаимно простые делители
Даны целые числа p и q. Получить все делители числа q, взаимно простые с p,...

Простые делители числа,задачка!
Задача:Простые делители числа 13195 - это 5, 7, 13 и 29. Какой самый большой...

Простые делители заданного числа
Задача из сборника Златопольского 8.54*. Дано натуральное число n. Получить...

Получить все простые делители числа
Здравствуйте, помогите, пожалуйста. Дано целое число n. Получить все простые...

Вывести все простые делители числа
Люди помогите с лабами до субботы надо сдать!!! 1. Ввести целое число N....

Получить все простые делители числа
Дано натуральное число n. Получить все простые делители этого числа. Помогите...

25
Humanitis
175 / 167 / 27
Регистрация: 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;
}
0
Новенький
44 / 9 / 3
Регистрация: 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;
}
вооще, виснет..
0
Humanitis
175 / 167 / 27
Регистрация: 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;
}

З.ы. Отладчиком пользоваться надо учиться
0
Новенький
44 / 9 / 3
Регистрация: 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, ты тут"???
0
Monte-Cristo
2794 / 1380 / 107
Регистрация: 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;
}
0
Evg
Эксперт CАвтор FAQ
18940 / 6901 / 513
Регистрация: 30.03.2009
Сообщений: 19,446
Записей в блоге: 30
23.04.2009, 23:44 #7
Monte-Cristo, у тебя квадратичный алгоритм. Исходя из поста #5 надо чтобы по времени быстро работало. Алгоритм Humanitis'а, похоже, этим свойством обладает, т.к. с такими делениями циклы получаются короткие. Правда матчасть этого алгоритма я не понимаю
0
Humanitis
175 / 167 / 27
Регистрация: 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;
}
0
Новенький
44 / 9 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:40  [ТС] #9
Humanitis, Это я понял... Но вот задачка мне нужна для чисел 10^9 степени....
0
Humanitis
175 / 167 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:56 #10
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
0
Новенький
44 / 9 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:58  [ТС] #11
Цитата Сообщение от Humanitis Посмотреть сообщение
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
проблемка в том что проверяющая системка __int64 не берет
0
Humanitis
175 / 167 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 09:01 #12
unsigned long
0
Новенький
44 / 9 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:12  [ТС] #13
Там из 65 тестов прошло 47, 17 неправильных ответов, 1 TLE time limit
0
Evg
Эксперт CАвтор FAQ
18940 / 6901 / 513
Регистрация: 30.03.2009
Сообщений: 19,446
Записей в блоге: 30
24.04.2009, 09:19 #14
Цитата Сообщение от Humanitis Посмотреть сообщение
unsigned long
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
0
Новенький
44 / 9 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:51  [ТС] #15
Цитата Сообщение от Evg Посмотреть сообщение
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
и так тож не получается
0
Humanitis
175 / 167 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:03 #16
Evg, Да даже 32 битный вмещает 10^9.
Новенький, Могу только посоветовать перед считыванием данных сгенирировать массив простых чисел от 3 до sqrt(10^9). потом просто в качестве делителей брать числа из этого массива. Так будет быстрее
0
Evg
Эксперт CАвтор FAQ
18940 / 6901 / 513
Регистрация: 30.03.2009
Сообщений: 19,446
Записей в блоге: 30
24.04.2009, 10:07 #17
Цитата Сообщение от Humanitis Посмотреть сообщение
Evg, Да даже 32 битный вмещает 10^9.
Изначальная постановка вопроса была "проблемка в том что проверяющая системка __int64 не берет", на что ты посоветовал использовать long. Я и возразил, что для 64-битного числа нужен long long. Лишь после твоего комментария я понял, что ты НЕ предлагал использовать long в качестве 64-битного значения, а просто попросил поменять __int64 на long, чтобы задача скомпилировалась.
0
Humanitis
175 / 167 / 27
Регистрация: 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
0
Новенький
44 / 9 / 3
Регистрация: 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;
}
0
Humanitis
175 / 167 / 27
Регистрация: 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;
}
0
24.04.2009, 10:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2009, 10:22
Привет! Вот еще темы с решениями:

Получить все делители числа q, взаимно простые с р
3.Даны натуральные числа р и q. Получить все делители числа q, взаимно простые...

Получить все простые делители заданного числа
Дано натуральное число n. Получить все простые делители этого числа. (нужно...

Найти все делители числа n, взаимно простые с m
Даны целые числа m и n. Найти все делители числа n, взаимно простые с m.

Получить все делители числа q, взаимно простые к p
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к...


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

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

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