주어진 범위 내에서 소수의 제수를 가진 총 개수 찾기

Question

범위는 1에서 1,000000000000까지입니다. 입력 : L 및 R 여기서 L-R < = 1,000,000 L 및 R은 1과 1,000000000000 사이의 값일 수 있습니다.

예

경우 L = 2 및 R = 5 다음 O/P : 4

이유 :

2- 1,2- 합계 2

-3- 1,3- 전체 소수 소수 2

4- 1,2,3- 합계 3 프라임 인 소수

5- 1,5- 합계 2

범위의 숫자 4는 제수가 소수입니다. 출력은 4입니다.

나는 체를 사용해 보았지만 시간이 많이 걸렸습니다. 더 나은 해결책을 제안 해 주시겠습니까?

Answer 1

접근 1 :

1. Calculate all prime numbers in the given range (2,R) using 
    sieve of eratosthenes. 
2. Initialize the result as number of primes(say NP) since all primes 
    are having prime number(2) of divisors. 
3. For each prime((P), we can generate maximum of NP - 1 numbers 
    that has prime number of divisors. 

    Let say P1,P2,P3,....Pn are prime numbers of range (L,R). 

    NP is the number of primes of range (L,R). 

    Each prime has 2(prime number of) divisors. 
    Square(3 - 1) of prime has 3 divisors. 
    4th power(5 - 1) of prime has 5 divisors. 
    ... 
    nth power(n + 1 (is prime) - 1) of prime has n+1 divisors. 

    Increment the result by 1 if pow(Pi, Pj -1) <= R, i >= L, j<=R and i != j 

Note : All primes in an array(AP) are increasing numbers(sorted), so we can 
     also use the modified binary search to find the numbers of 
     prime divisors in a given range 

접근 2 : (내 동료에 의해 제안 나 개선)

1. Create a divisors array that can hold R - L - 1 number of elements and 
    initialize it to zero. 
2. Iterate i from L to R 
3. Check if divisors(i) <> 0. Go to step 2 if divisors(i) = 0. 
4. compute the absolute difference of number of divisors of i and i * p (prime). 
5. The absolute difference between the number of divisors of i, i * p and 
    i*p, i*p*p are same. 
     a = number of divisor of i 
     d = difference of number of divisors of i * 2 and i. 
     divisors(i-L) = a 
     p = 2(prime number) 
     n = distance from a in arithemetic progression 
     iterate j from i * p to R, j = j * p 
      divisors(j-L) = a + n * d 
      n = n + 1 
6) Filter divisors array to find prime number of divisors