Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.70/23: Рейтинг темы: голосов - 23, средняя оценка - 4.70
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254

Простые делители

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

Студворк — интернет-сервис помощи студентам
Требуется написать программу которая находит сумму простых делителей числа n
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
23.04.2009, 22:27
Ответы с готовыми решениями:

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

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

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

25
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
23.04.2009, 22:39
Не проверял на работоспособность
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
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
23.04.2009, 22:44  [ТС]
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
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
23.04.2009, 22:48
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
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
23.04.2009, 23:04  [ТС]
Цитата Сообщение от 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
2816 / 1408 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
23.04.2009, 23:25
попробуйте так...
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
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
23.04.2009, 23:44
Monte-Cristo, у тебя квадратичный алгоритм. Исходя из поста #5 надо чтобы по времени быстро работало. Алгоритм Humanitis'а, похоже, этим свойством обладает, т.к. с такими делениями циклы получаются короткие. Правда матчасть этого алгоритма я не понимаю
0
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:38
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
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:40  [ТС]
Humanitis, Это я понял... Но вот задачка мне нужна для чисел 10^9 степени....
0
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 08:56
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
0
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 08:58  [ТС]
Цитата Сообщение от Humanitis Посмотреть сообщение
Новенький, Тип данных выбирай подходящий(например unsigned __int64) и будет тебе счастье
проблемка в том что проверяющая системка __int64 не берет
0
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 09:01
unsigned long
0
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:12  [ТС]
Там из 65 тестов прошло 47, 17 неправильных ответов, 1 TLE time limit
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
24.04.2009, 09:19
Цитата Сообщение от Humanitis Посмотреть сообщение
unsigned long
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
0
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 09:51  [ТС]
Цитата Сообщение от Evg Посмотреть сообщение
ДЛя 32-битных систем нужен unsigned long long
Т.е. unsigned long там как правило 32-битный. long обычно делают совпадающим с размером адреса
и так тож не получается
0
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:03
Evg, Да даже 32 битный вмещает 10^9.
Новенький, Могу только посоветовать перед считыванием данных сгенирировать массив простых чисел от 3 до sqrt(10^9). потом просто в качестве делителей брать числа из этого массива. Так будет быстрее
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
24.04.2009, 10:07
Цитата Сообщение от Humanitis Посмотреть сообщение
Evg, Да даже 32 битный вмещает 10^9.
Изначальная постановка вопроса была "проблемка в том что проверяющая системка __int64 не берет", на что ты посоветовал использовать long. Я и возразил, что для 64-битного числа нужен long long. Лишь после твоего комментария я понял, что ты НЕ предлагал использовать long в качестве 64-битного значения, а просто попросил поменять __int64 на long, чтобы задача скомпилировалась.
0
 Аватар для Humanitis
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:17
Новенький,
Попробуй еще это вставить
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
45 / 10 / 3
Регистрация: 03.03.2009
Сообщений: 254
24.04.2009, 10: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
176 / 168 / 27
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 10:22
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
24.04.2009, 10:22
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Функция заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru