I (2 балла). Суммирование по составным Все языки (Make) Clang 16.0.0 C++20 Ограничение…
- User
I (2 балла). Суммирование по составным Все языки (Make) Clang 16.0.0 C++20 Ограничение времени 2 секунды 1 секунда Ограничение памяти 64Mb 16Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Легенда подготовлена в соавторстве с Beremcool. Математик Харди хочет представить своего коллегу Рамануджана лучшему комбинаторику Кембриджа майору Макмэхону. Макмэхон проверял математиков на возможности счета. А именно, он просил для заданного N найти сумму наименьших простых делителей всех составных чисел, больших 2 и не превосходящих N. Если ответ давался не моментально или был некорректным, то Макмэхон не продолжал беседу с математиком. Вы в лице Харди хотите подготовить Рамануджана к встрече с майором. Помогите индийскому математику научиться быстро просеивать сквозь решето. Формат ввода Первая строка входных данных содержит одно целое число NS 10° Формат вывода Выведите одно целое число - ответ к задаче. Пример 1 Ввод Вывод Пример 2 Ввод Вывод реши на питоне
- Assistant
The problem requires calculating the sum of the smallest prime factors of all composite numbers greater than 2 and less than or equal to a given integer ( N ) (( N \leq 10^8 )). Due to the constraints on execution time and memory, we need an efficient algorithm.
Here's a Python solution using the segmented sieve method:
import sys import math def compute_sum_of_smallest_prime_divisors(N): max_N = N limit = int(math.isqrt(N)) + 1 # Generate all prime numbers up to sqrt(N) is_prime = [True] * (limit) is_prime[0] = is_prime[1] = False for i in range(2, int(limit**0.5)+1): if is_prime[i]: for j in range(i*i, limit, i): is_prime[j] = False primes = [i for i, val in enumerate(is_prime) if val] segment_size = 5000000 # Adjust based on memory limits answer = 0 for low in range(3, N+1, segment_size): high = min(low + segment_size - 1, N) size = high - low + 1 spf = [0]*size # Smallest prime factor for segment for p in primes: start = max(p*p, ((low + p - 1) // p) * p) for j in range(start, high+1, p): idx = j - low if spf[idx] == 0: spf[idx] = p for i in range(size): n = low + i if n > 2 and spf[i] > 0: answer += spf[i] return answer if __name__ == '__main__': import threading import sys def main(): N = int(sys.stdin.readline()) ans = compute_sum_of_smallest_prime_divisors(N) print(ans) threading.Thread(target=main).start()This code first precomputes all prime numbers up to ( \sqrt{N} ) using the Sieve of Eratosthenes. Then it processes numbers from 3 to ( N ) in segments (to stay within memory limits). For each segment, it initializes an array to hold the smallest prime factors and applies the sieve using the precomputed primes.
Finally, it sums up the smallest prime factors of the composite numbers in each segment and adds them to get the final answer.
This implementation considers efficiency in both time and memory:
-
Time: The algorithm avoids unnecessary calculations and uses efficient looping structures. Precomputing primes only up to ( \sqrt{N} ) reduces the number of primes to consider.
-
Memory: Segmenting allows the processing of large ranges without exceeding the memory constraints. The size of each segment is chosen based on the available memory limit.
We use the standard input/output for reading the input ( N ) and printing the answer, as specified in the problem statement.
-