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

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

23.04.2009, 22:27. Показов 4874. Ответов 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
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru