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 2ⁿ-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