День 1. Разбор задач.
Нетривиальные числа
Тривиальность = (Сумма всех делителей) / $N$.
Рассмотрим тривиальность различных чисел:
| $\frac{1}{ 2 }=\frac{ 1 }{ 2 }= 0.5 $ |
| $\frac{1}{ 3 }=\frac{ 1 }{ 3 }= 0.3333333333333333 $ |
| $\frac{1+2}{ 4 }=\frac{ 3 }{ 4 }= 0.75 $ |
| $\frac{1}{ 5 }=\frac{ 1 }{ 5 }= 0.2 $ |
| $\frac{1+2+3}{ 6 }=\frac{ 6 }{ 6 }= 1.0 $ |
| $\frac{1}{ 7 }=\frac{ 1 }{ 7 }= 0.14285714285714285 $ |
| $\frac{1+2+4}{ 8 }=\frac{ 7 }{ 8 }= 0.875 $ |
| $\frac{1+3}{ 9 }=\frac{ 4 }{ 9 }= 0.4444444444444444 $ |
| $\frac{1+2+5}{ 10 }=\frac{ 8 }{ 10 }= 0.8 $ |
| $\frac{1}{ 11 }=\frac{ 1 }{ 11 }= 0.09090909090909091 $ |
| $\frac{1+2+3+4+6}{ 12 }=\frac{ 16 }{ 12 }= 1.3333333333333333 $ |
| $\frac{1}{ 13 }=\frac{ 1 }{ 13 }= 0.07692307692307693 $ |
Можно заметить, что для простых чисел тривиальность минимальна.
Итак, нам нужно найти наибольшее простое число из диапазона $[a,b]$ или (если в диапазоне нет ни одного простого числа), то число с наименьшей тривиальностью.
Числа до $10^6$, тогда у составных чисел хотя бы один из множителей не больше $10^3$ и простые числа встречаются не реже чем раз в 1000 чисел, поэтому достаточно проверить интервал $[b-1000,b]$, если $b - 1000 > a$.
Реализация на Python
# Наибольшее простое число в отрезке [a, b]: перебор от b вниз, проверка делением, O(len * sqrt(b))
from math import isqrt
def is_prime(n):
"""Число простое, если у него нет делителей от 2 до sqrt(n)."""
if n < 2:
return False
for divisor in range(2, isqrt(n) + 1):
if n % divisor == 0:
return False
return True
def largest_prime(a, b):
"""Идем от b вниз до a и возвращаем первое простое число; если простых нет, возвращаем None."""
for number in range(b, a - 1, -1):
if is_prime(number):
return number
return None
if __name__ == "__main__":
print("Наибольшее простое в [1, 100]:", largest_prime(1, 100))
print("Наибольшее простое в [90, 96]:", largest_prime(90, 96))
print("Наибольшее простое в [1, 10^6]:", largest_prime(1, 10**6))
Реализация на C++
// Наибольшее простое число в отрезке [a, b]: перебор от b вниз, проверка делением, O(len * sqrt(b))
#include <cstdio>
bool isPrime(long long n) {
if (n < 2) return false;
for (long long d = 2; d * d <= n; ++d) {
if (n % d == 0) return false;
}
return true;
}
// Возвращает наибольшее простое число в [a, b] или -1, если простых чисел в отрезке нет
long long largestPrime(long long a, long long b) {
for (long long number = b; number >= a; --number) {
if (isPrime(number)) return number;
}
return -1;
}
int main() {
std::printf("Наибольшее простое в [1, 100]: %lld\n", largestPrime(1, 100));
std::printf("Наибольшее простое в [90, 96]: %lld\n", largestPrime(90, 96));
std::printf("Наибольшее простое в [1, 10^6]: %lld\n", largestPrime(1, 1000000));
return 0;
}
Реализация на Rust
// Наибольшее простое число в отрезке [a, b]: перебор от b вниз, проверка делением, O(len * sqrt(b))
pub fn is_prime(n: u64) -> bool {
if n < 2 {
return false;
}
let mut d = 2;
while d * d <= n {
if n % d == 0 {
return false;
}
d += 1;
}
true
}
// Наибольшее простое число в [a, b]; None, если простых чисел в отрезке нет
pub fn largest_prime(a: u64, b: u64) -> Option<u64> {
(a..=b).rev().find(|&number| is_prime(number))
}
fn main() {
println!("Наибольшее простое в [1, 100]: {:?}", largest_prime(1, 100));
println!("Наибольшее простое в [90, 96]: {:?}", largest_prime(90, 96));
println!("Наибольшее простое в [1, 10^6]: {:?}", largest_prime(1, 1_000_000));
}
Как быстро посчитать тривиальность числа?
from math import sqrt
# Вычисляем тривиальность N
def trivial(N):
if N == 1: # У единицы нет собственных делителей
return 0
sum = 1 # Сумма делителей
for i in range(2, int(sqrt(N)) + 1): # Пробегаем числа i от 2 до корня из N
if N % i == 0: # Если N делится на i
sum += i
ii = N // i # Парный делитель N = i * ii
if ii != i: # Если он не равен i, то добавляем и его
sum += ii
return sum / N
Реализация на C++
// Сумма собственных делителей N (без самого N) перебором до sqrt(N), O(sqrt(N)) времени
#include <cstdio>
long long properDivisorSum(long long n) {
if (n == 1) return 0; // у единицы нет собственных делителей
long long sum = 1; // делитель 1 есть у любого N > 1
for (long long i = 2; i * i <= n; ++i) {
if (n % i != 0) continue;
sum += i;
const long long pair = n / i; // парный делитель: n = i * pair
if (pair != i) sum += pair; // при i = sqrt(n) пару не добавляем
}
return sum;
}
int main() {
const long long numbers[] = {1, 2, 4, 6, 12, 13};
for (long long n : numbers) {
const long long sum = properDivisorSum(n);
const double triviality = static_cast<double>(sum) / static_cast<double>(n);
std::printf("N=%lld: сумма делителей=%lld, тривиальность=%.6f\n", n, sum, triviality);
}
return 0;
}
Реализация на Rust
// Сумма собственных делителей N (без самого N) перебором до sqrt(N), O(sqrt(N)) времени
pub fn proper_divisor_sum(n: u64) -> u64 {
if n == 1 {
return 0; // у единицы нет собственных делителей
}
let mut sum = 1; // делитель 1 есть у любого N > 1
let mut i = 2;
while i * i <= n {
if n % i == 0 {
sum += i;
let pair = n / i; // парный делитель: n = i * pair
if pair != i {
sum += pair; // при i = sqrt(n) пару не добавляем
}
}
i += 1;
}
sum
}
fn main() {
for n in [1, 2, 4, 6, 12, 13] {
let sum = proper_divisor_sum(n);
let triviality = sum as f64 / n as f64;
println!("N={n}: сумма делителей={sum}, тривиальность={triviality:.6}");
}
}