Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def sumDistinct(N):
- MAXN = 1000001
- spf = [0 for i in range(MAXN)]
- adj = [[] for i in range(MAXN)]
- spf[1] = 1
- for i in range(2, MAXN):
- spf[i] = i
- for i in range(2, MAXN):
- if i * i > MAXN: break
- if (spf[i] == i):
- for j in range(i * i, MAXN, i):
- if (spf[j] == j):
- spf[j] = i
- index = 0
- for i in range(1, N + 1):
- index = 1
- x = i
- if(x != 1):
- adj[i].append(spf[x])
- x = x // spf[x]
- while (x != 1):
- if (adj[i][index - 1] != spf[x]):
- adj[i].append(spf[x])
- index += 1
- x = x // spf[x]
- return sum(sum(k) for k in adj)%(10**9 +7)
Add Comment
Please, Sign In to add comment