Статья Автор: Лебедев Дмитрий Алексеевич

Работа с числами - простые, делители, функции

Программа поиска минимального делителя натурального числа mindel (n)
Использование :

Проверка на простоту n == mindel(n)
Факторизация числа и как варианты - количество делителей, сумма делителей, число Эйлера

def mindel(n):
   if n % 2 == 0 : return 2
   if n < 9 : return n
   p = 3
   while (n % p != 0) and (p * p < n) : p+=2
   if p * p > n : p = n
   return p
n = int(input())
p = mindel(n)
if p == n : print(f'число {n} is prime (или 1)')
else : print(f'число {n} is composite ({n} = {p} * {n//p})')

#include <iostream>

using namespace std;

int mindel(int n){
   if (n % 2 == 0) {return 2;}
   if (n < 9) {return n;}
   int p = 3;
   while ((n % p != 0) and (p * p < n)) {p+=2;}
   if (p * p > n) {p = n;}
   return p; 
  }
int main() {
  int n, p;
  cin >> n;
  p = mindel(n);
  if (p == n) {printf("number %d is prime (or 1)", n);}
  else {printf("number %d is composite (%d * %d)",n, p, n/p);}
  return 0;
}

Факторизация числа fact(n)
Если \(\)\(n = p_1^{r_1}\cdot_{\dots}\cdot p_k^{r_k}\) то программа должна вернуть словарь вида \(D[p_i] = r_i\)
При решении будем использовать программу mindel (которую скроем для удобства)
Программа возвращает словарь "факторизации", на базе которого вычисляется:

a - количество простых делителей числа
b - количество всех делителей числа (включая 1 и само число) \(\sigma(n)\)
c - сумму всех делителей числа (включая 1 и само число) \(\tau(n)\)
d - число Эйлра \(\varphi(n)\) = количеству всех натуральных чисел, не превосходящих само число,
взаимно простых с ним

def fact(n):
  F = {}
  while n > 1 :
    d = mindel(n)
    k = 0
    while n % d == 0 :
      k += 1
      n = n // d
    F[d] = k
  return F  
    

n = int(input())
D = fact(n)
a, b, c, d = len(D), 1, 1, n
for p in D :
  k = D[p]
  b = b * (k + 1)
  c = c * ((p**(k+1)-1)//(p-1))
  d = (d // p) * (p - 1)
print(f'факторизация {n} = {D}')
print(f'простых делителей = {a}')
print(f'всего делителей = {b}')
print(f'сумма делителей = {c}')
print(f'взаимно простых с {n} = {d if n > 1 else 0}')

#include <iostream>
#include <map>
#include<cmath>

using namespace std;

int mindel(int n){
   if (n % 2 == 0) {return 2;}
   if (n < 9) {return n;}
   int p = 3;
   while ((n % p != 0) and (p * p < n)) {p+=2;}
   if (p * p > n) {p = n;}
   return p; 
  }
auto fact(int n){
  map <int, int> F ;
  while (n > 1){
    int d = mindel(n);
    int k = 0;
    while (n % d == 0){
      k += 1;
      n = n / d;
    }
    F[d] = k;
  }  
  return F;
  }

int main() {
  int n;
  cin >> n;
  auto D = fact(n);
  int a = D.size(), b = 1, c = 1, d = n;
  printf("factors : ");
  for (auto [p, k] : D){
    printf("%d ^ %d, ", p, k);
    b = b * (k+1);
    c = c * ((pow(p,k+1) - 1)/(p - 1));
    d = (d / p) * (p - 1);
  }
  printf("\nprime divisors = %d \n", a);
  printf("number of divisors = %d \n", b);
  printf("the sum of a number's divisors = %d \n", c);
  printf("Euler's number = %d ", (n > 1) ? d : 0);
  return 0;
}

Печать