We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
import math
import os
import random
import re
import sys
isprime = [True] * 1000000
prime = []
SPF = [None] * 1000000
def manipulated_seive(N):
# 0 and 1 are not prime
isprime[0] = isprime[1] = False
# Fill rest of the entries
for i in range(2, N):
# If isPrime[i] == True then i is
# prime number
if isprime[i] == True:
# put i into prime[] vector
prime.append(i)
# A prime number is its own smallest
# prime factor
SPF[i] = i
# Remove all multiples of i*prime[j]
# which are not prime by making is
# Prime[i * prime[j]] = false and put
# smallest prime factor of i*Prime[j]
# as prime[j] [ for exp :let i = 5 , j = 0 ,
# prime[j] = 2 [ i*prime[j] = 10 ]
# so smallest prime factor of '10' is '2'
# that is prime[j] ] this loop run only one
# time for number which are not prime
j = 0
while (j < len(prime) and
i * prime[j] < N and
prime[j] <= SPF[i]):
isprime[i * prime[j]] = False
# put smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j]
j += 1
def solve(n):
# Write your code here
manipulated_seive(n+1)
power=[]
for i in prime:
lim=int(math.log(n,i))
s=sum([n//(i**j) for j in range(1,lim+1)])
power.append(s)
result=1
for i in power:
result*=2*i+1
return result%1000007
if name == 'main':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input().strip())
result = solve(n)
fptr.write(str(result) + '\n')
fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Equations
You are viewing a single comment's thread. Return to all comments →
!/bin/python3
import math import os import random import re import sys
isprime = [True] * 1000000 prime = [] SPF = [None] * 1000000 def manipulated_seive(N): # 0 and 1 are not prime isprime[0] = isprime[1] = False
def solve(n): # Write your code here manipulated_seive(n+1) power=[] for i in prime: lim=int(math.log(n,i)) s=sum([n//(i**j) for j in range(1,lim+1)]) power.append(s) result=1 for i in power: result*=2*i+1 return result%1000007
if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')