프로그램 명: coci_snaga
제한시간: 1 초
유한한 길이의 수열 P를 생각하자. P1=N이고, Pk+1은 Pk의 약수가 아닌 최소 자연수이다. 이 수열은 Pk+1을 구할 수 없을 때까지 이어진다.
N=6인 경우, 수열 P는 6, 4, 3, 2가 나열된다.
함수 f(N)은 첫 번째 항이 N인 수열 P의 원소의 개수이다. 위의 경우에서는 f(6)=4임을 알 수 있다.
A < B인 두 양의 자연수 A, B가 주어질 때, 다음 값을 구하는 프로그램을 작성하여라.
f(A)+f(A+1)+…+f(B)
입력 형식
A와 B가 입력된다. 3 ≤ A < B < 10^17
출력 형식
f(A)+f(A+1)+…+f(B)의 값을 출력한다.
Let us begin with a positive integer N and find the smallest positive integer which doesn't divide N.
If we repeat the procedure with the resulting number, then again with the new result and so on, we will
eventually obtain the number 2 (two). Let us define strength(N) as the length of the resulting
sequence.
For example, for N = 6 we obtain the sequence 6, 4, 3, 2 which consists of 4 numbers, thus strength(6) = 4.
Given two positive integers A < B, calculate the sum of strengths of all integers between A and B
(inclusive), that is,
strength(A) + strength(A + 1) + ... + strength(B).
입력
The first and only line of input contains two positive integers, A and B (3 ≤ A < B < 10^17).
출력
The first and only line of output should contain the requested sum of strengths.
입출력 예
input
3 6
output
11
input
100 200
output
262
출처:coci/2012-2013/contest1 5/6
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]