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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
yura332
0 / 0 / 0
Регистрация: 21.09.2009
Сообщений: 25
#1

Элементарные делители натурального числа - C++

21.09.2009, 15:16. Просмотров 1264. Ответов 6
Метки нет (Все метки)

есть натуральное число n. Получить все элементарные делители этого числа.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.09.2009, 15:16     Элементарные делители натурального числа
Посмотрите здесь:

Найти все делители натурального числа n C++
Вывести все делители заданного натурального числа с++ C++
Найти все делители натурального числа N C++
C++ помогите найти все делители натурального числа N
C++ Найти все простые положительные делители данного натурального числа
C++ Циклические алгоритмы: вывести на экран все простые делители заданного натурального числа
Делители натурального числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
21.09.2009, 15:59     Элементарные делители натурального числа #2
а в чём проблемма? существуют таблицы элементарных делителей. выбери первых надцать и как массив констант забей. потом проверяй если твоё n к ним не относиться дели по очереди на наименьшее, то есть на 2. на два не делиться дели на 3 и так далее. после каждой операции деления опять проверяй не стало оно равным элементарному делителю. стало отработала программа, не стала дели дальше.
Метод конечно топорный, зато самый простой.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
21.09.2009, 16:12     Элементарные делители натурального числа #3
Элементарные делители - это простые числа.
Получаем ряд простых чисел.
Делим n на каждое простое число, пока делится.
Окончание процесса - когда n станет равным 1.

Добавлено через 1 минуту
Простые числа бывают очень большие, так что забивать константный массив простых чисел от 2 до 2**31-1 как-то криво
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
21.09.2009, 16:33     Элементарные делители натурального числа #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//многа букоф...
  cout<<"Элементарные делители числа "<<n<<":"<<endl;
  if(n<=2)
    cout<<"Не смешно вводить такие цифры)";
  for(int i=2;i<n;i++)
    if(simpleInt(i) && n%i)
      cout<<i<<", ";
    
//многа букоф...
 
//Тест простоты по теореме Вильсона:
//p простое тогда и только тогда, когда (p-1)! + 1 делится на p
int factorial(int x) {
    if( x == 0 ) return 1;
    return x * factorial (x - 1);
}
bool simpleInt (int p)
{
  return ((factorial (p-1)+1)%p==0);
}
PS цикл можно (и нужно) упростить, сократив количество проходов
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
21.09.2009, 16:35     Элементарные делители натурального числа #5
Получаем ряд простых чисел.
именно чтобы не получать.
всё зависит от размерности этого n. может там до второго порядка
P.S. простые числа до сих пор вроде ищут, и даже деньги сулят тому кто найдёт.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
21.09.2009, 16:37     Элементарные делители натурального числа #6
2GAV_13: Проверь свою функцию simpleInt() хотя бы при p==20.
Просто 19! - это очень большое число

Добавлено через 1 минуту
2TanT: проблемы получить простые числа нет.
Можно без массива, можно с массивом.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2009, 16:49     Элементарные делители натурального числа
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
21.09.2009, 16:49     Элементарные делители натурального числа #7
odip, дык я для примера) можно и другие тесты простоты взять
Yandex
Объявления
21.09.2009, 16:49     Элементарные делители натурального числа
Ответ Создать тему
Опции темы

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