Skip to content

Latest commit

 

History

History
34 lines (30 loc) · 1.35 KB

README.md

File metadata and controls

34 lines (30 loc) · 1.35 KB
Raw

  • PREREQUISITE : Sieve , Prime factorisation , Factorial Factorisation

  • Explanation :



Basic Idea was actually taken from the method of Precalculating No of divisors and sum of divisors . for every power of every prime less than N we added 1 to it's multple . a small example is described below .

suppose from 1 to 15 initially the array was

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

for 2^1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0


for 2^2

0 1 0 2 0 1 0 2 0 1 0 2 0 1 0


for 2^3

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0


for 3^1

0 1 1 2 0 2 0 3 1 1 0 3 0 1 1


for 3^2
0 1 1 2 0 2 0 3 2 1 0 3 0 1 1

for 5^1
0 1 1 2 1 2 0 3 2 2 0 3 0 1 2

for 7^1
0 1 1 2 1 2 1 3 2 2 0 3 0 2 2

for 11^1
0 1 1 2 1 2 1 3 2 2 1 3 0 2 2

for 13^1
0 1 1 2 1 2 1 3 2 2 1 3 1 2 2

Now cummlative sum of the array 0 1 2 4 5 7 8 11 13 15 16 19 20 22 24

here the total time complexity will be O( No of primes up to N * log2(N) * log10(log10(N)) ) suppose the N is 10^6 then No of primes will be near 78500 . so it will take 78500*log2(10^6)*log10(log10(10^6)) ) = 1.2 * 10^6 which is a much better solution and not get TLE .