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

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

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

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

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

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

Взаимно простые делители - C++
Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей. Помогите пожалуйста...

Простые делители заданного числа - C++
Задача из сборника Златопольского 8.54*. Дано натуральное число n. Получить все простые делители этого числа #include <iostream> ...

Простые делители числа,задачка! - C++
Задача:Простые делители числа 13195 - это 5, 7, 13 и 29. Какой самый большой делитель числа 600851475143, являющийся простым числом? ...

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

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

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

25
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;
}
0
Новенький
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;
}
вооще, виснет..
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;
}

З.ы. Отладчиком пользоваться надо учиться
0
Новенький
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, ты тут"???
0
Monte-Cristo
2790 / 1376 / 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;
}
0
Evg
Эксперт CАвтор FAQ
18029 / 6261 / 427
Регистрация: 30.03.2009
Сообщений: 17,200
Записей в блоге: 27
23.04.2009, 23:44 #7
Monte-Cristo, у тебя квадратичный алгоритм. Исходя из поста #5 надо чтобы по времени быстро работало. Алгоритм Humanitis'а, похоже, этим свойством обладает, т.к. с такими делениями циклы получаются короткие. Правда матчасть этого алгоритма я не понимаю
0
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;
}
0
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:40  [ТС] #9
Humanitis, Это я понял... Но вот задачка мне нужна для чисел 10^9 степени....
0
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:56 #10
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
0
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:58  [ТС] #11
Цитата Сообщение от Humanitis Посмотреть сообщение
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
проблемка в том что проверяющая системка __int64 не берет
0
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 09:01 #12
unsigned long
0
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:12  [ТС] #13
Там из 65 тестов прошло 47, 17 неправильных ответов, 1 TLE time limit
0
Evg
Эксперт CАвтор FAQ
18029 / 6261 / 427
Регистрация: 30.03.2009
Сообщений: 17,200
Записей в блоге: 27
24.04.2009, 09:19 #14
Цитата Сообщение от Humanitis Посмотреть сообщение
unsigned long
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
0
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:51  [ТС] #15
Цитата Сообщение от Evg Посмотреть сообщение
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
и так тож не получается
0
24.04.2009, 09:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2009, 09:51
Привет! Вот еще темы с ответами:

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

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

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

Получить все простые делители заданного числа - C++
Дано натуральное число n. Получить все простые делители этого числа. (нужно использовать функцию) #include &lt;iostream&gt; #include...


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

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

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