roy-and-shopping-20

Alfi asked Roy to go for shopping with her. Witty Roy came up with a condition. He said, for each product of MRP (Maximum Retail Price) R, she'll have to pay minimum of all the prime factors of R and he himself will pay rest of the amount. Without giving it a second thought Alfi agreed. 

Now they bought N number of products. You're to find how much money did Roy had to pay for each product.

Input:

First line will contain integer N, number of products they bought.

Next N lines each will contain R, MRP of each product.

Output:

Print single integer in a new line, the amount of money Roy had to pay for each product.

Constraints:

2 ≤ N,R ≤ 1000000

Warning:
Large I/O. Be careful with certain languages.

SAMPLE INPUT
2
5
10

SAMPLE OUTPUT
0
8

Explanation

Test Case #1: Only 1 prime factor of 5 is 5 itself, so Alfi will pay all the money and hence Roy has to pay 0.

Test Case #2: Prime Factors of 10 are 2 and 5, minimum of these is 2, so Alfi pays 2 and hence Roy has to pay the rest, which is 8.

Source: hackerearth | Difficulty: EASY
Tags: Mathematics


Solutions:
from sys import stdin
N = 1000001
prime = [0]*N
lpf = [0]*N
prime[0] = 1
prime[1] = 1
def lpf_sieve():
	for i in range(N):
		lpf[i] = i
	i = 2
	while i*i <= N:
		j = 2*i
		if prime[i] != 1: 
			while j < N:
				if lpf[j] > i:
					lpf[j] = i
				prime[j] = 1
				j += i
		i += 1
def abcd():
	data = (line for line in stdin.read().splitlines())
	#T = input()
	T = int(next(data))
	lpf_sieve()
	for i in range(T):
		#R = input()
		R = int(next(data))
		print(R-lpf[R])
abcd()


import math
max=10**6+6
sieve = [0] * max
for p in range(2, max):
	if not sieve[p]:
	   for i in range(p, max, p):
	       if sieve[i]==0:
		   sieve[i]=p

for _ in range(eval(input())):
  n= eval(input())
  print(n-sieve[n])