th0m45s5helby

Untitled

Jan 27th, 2022 (edited)
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.88 KB | None | 0 0
  1. def sumDistinct(N):
  2.     MAXN = 1000001
  3.     spf = [0 for i in range(MAXN)]
  4.     adj = [[] for i in range(MAXN)]
  5.    
  6.     spf[1] = 1
  7.     for i in range(2, MAXN):
  8.         spf[i] = i
  9.    
  10.     for i in range(2, MAXN):
  11.         if i * i > MAXN: break
  12.        
  13.         if (spf[i] == i):
  14.            
  15.             for j in range(i * i, MAXN, i):
  16.                
  17.                 if (spf[j] == j):
  18.                     spf[j] = i
  19.                    
  20.                    
  21.     index = 0
  22.     for i in range(1, N + 1):
  23.         index = 1
  24.         x = i
  25.         if(x != 1):
  26.             adj[i].append(spf[x])
  27.            
  28.         x = x // spf[x]
  29.        
  30.         while (x != 1):
  31.             if (adj[i][index - 1] != spf[x]):
  32.                 adj[i].append(spf[x])
  33.                 index += 1
  34.            
  35.             x = x // spf[x]
  36.    
  37.     return sum(sum(k) for k in adj)%(10**9 +7)
  38.  
  39.  
  40.  
  41.  
Add Comment
Please, Sign In to add comment