Skip to main content

PRIME DISTANCE : MINDSTORMER - APR20

PRIME DISTANCE - MINDSTORMER

QUESTION BRIEF :

In the question A number X(secret no) was given to you, and you had to recursively do following things.

  • Represent X in the form of 2n-z 
  • Find Nearest Prime no(y) to z
  • Assign x=y
Repeat the process, untill x becomes less than or equal to 2, because there is no prime no less than 2.

Prerequisite : Preprocessing, Recursion,Brute Force

Approach :

According to constraint, x may be upto 500000 and the no of queries asked for x might be upto 100000.
So for perfect solution , all the three points must be done not more than O(1) for a step and for any starting value of x , it will converge to 2 very quickly.
  • Preprocessing :
For number ranging from 1 to 1000000, we will store these three calculations already 
  1. Prime no just less than it
  2. Bool (True or False) if current no is a prime
  3. Just next big Power of 2
Do Recursion and do each iteration in O(1) only.
  • Algorithm :
  1. Intialize a list or "array of tuple" of [1000000][3] with default value [0,False,0]
  2. Run Seive Algorithm and correct the bool specified for list, change False to True for prime positions
  3. Make an array or list of size 20 since (2^20 > 1000000) and store the power of 2 in it.Also change the 3rd value of index(2^i) in list initialized in step 1 with index of the array(i)
  4. Now start with list initialized in step 1 , and do following change, and update the  following thing: Previous prime no, next index of power 2 (i.e. 1st and 3rd value)
  5. Do Recursion as you want either with DP or Loop
Setter Code :
    Uncomment all the print command , What's happening inside the code will be printed.
p_arr=[]
arr=[[0,True,0] for i in range(1000001)]
def preprocess():
arr[0][1]=False
arr[1][1]=False
arr[2][2]=2
p=2
while(p*p<=1000001):
#print(p,arr[p][1])
if(arr[p][1]==True):
for i in range(p*p,1000001,p):
arr[i][1]=False
p+=1
#Jump for nearest Prime
prev=2
for i in range(3,1000001):
if(arr[i][1]==True):
prev=i
arr[i][2]=prev
#power of 2
for i in range(20):
arr[2**i][0]=i
p_arr.append(2**i)
prev=1
for i in range(1000001):
if(arr[i][0]>0):
prev+=1
else:
arr[i][0]=prev
def dp(n):
#print(n)
if(n<=2):
return 0
else:
p=arr[n][2]
diff=p_arr[arr[p][0]]-p
#print('{}=2**{}-{}'.format(p,arr[p][0],diff))
return diff+dp(diff)
def main():
preprocess()
t=int(input())
for i in range(t):
n=int(input())
sm=dp(n)
print((sm%1000000007))
if __name__=="__main__":
main()
view raw prime_distance.py hosted with ❤ by GitHub

Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

Brilliant Mind - Mindstormer April 20 (Product Of All Perfect Square Term Upto A Given No 'n')

Product Of All Perfect Square Term Upto n Question Brief   :           A Number 'n' is given to you , you are said to find the product of all the perfect square term less than or equal to n. Prequisite   :   Basic Mathematics, Preprocessing Approach   :      Perfect Square numbers upto any number n are only these:          (1 2 ,2 2 ,........,(√n) 2 )      In Question it was asked to find the product of all perfect square numbers.i.e. ans =  (1 2  x 2 2   x....... x (√n) 2 ) it can be easily transformed to: ans =  (1   x 2   x....... x √n ) 2 ans= (√n!) 2 So, in each query , for given value of any n, we had to print the square of factorial of square root of n. This can be easily answered in O(1) if we already preprocess the number 1 to sqrt(N) and store their factorial already. SETTER CODE  :
Post a Comment
Read more

The Thinker's Thesaurus - Mindstormer April 20

Satisfy the condition: x*p^x ≡ q (mod r) Problem Brief   : Tanu is a pre final year cs student. She has been given an integer I. And has been asked to compute how many integers x ( 1 <= x <= I) satisfy the below condition:- x*p x   ≡  q (mod r) Prerequisite   :    Basic Mathematics Approach   : Brute force solution won't work as 'I' is in range of 10^10 .  So we need to find out some features of that given equation. We have p r-1 ≡1(mod r) where r is a prime number by  Fermat's Little Theorem , it is obvious that p z  mod r falls into a loop and the looping section is r−1. Also, z mod r has a looping section r .We can try to list a chart to show what  x*p x  is with some specific i,j. (In the chart shown below, x is equal to i*(r-1) + j. Proof for the chart shown above: For a certain i,j  we can see that  x *p^x mod r= ((i*(r−1)+j)mod r)* x ^ (i...
Post a Comment
Read more