Problem: Collection of pens

Everyone have some habits to collect one thing or the other. Harshit also has the craze to collect pens but in 3 piles. In first pile, he collected A pens and in the second pile, he collected B pens but in the third and the last pile , he think of something different. He decided to collect only the minimum number of pens in third pile so that the sum of pens in the three piles will give him a prime number. Note: there should be atleast one pen in the third pile.

Input:

First line contains the test cases,t. Then T test cases follow. Each line of the test case two space separated values A,B ie. number of pens in first and
second pile respectively.

Output:
Print the minimum number of pens that should be there in the third pile so that sum of all three piles produces a prime number.

Constraints:
1<=T<=30
1<=A<=1000
1<=B<=1000

Example:

Input:
2
1 3
4 3

Output
1
4

Explanation:

In first case,Harshit put one pen in first pile and 3 pens in second pile which give 4 as a sum.So if he adds one pen in the third pile, the sum will yield a prime number ie.5
Therefore the answer is 1.
Similarly for other test case

Python 2.7

 

from math import *
def make_primes():
    sieve_eratosthenes = [True]*3001
    for i in range(2, int(sqrt(len(sieve_eratosthenes)))):
        if sieve_eratosthenes[i]:
            temp = i+i
            for j in range(temp,len(sieve_eratosthenes),i):
                sieve_eratosthenes[j] = False
    result = []
    for i in range(2, len(sieve_eratosthenes)):
        if sieve_eratosthenes[i]:
            result.append(i)
    return result

if __name__ == '__main__':
    t = input()
    primes = make_primes()
    for _ in range(t):
        a, b = map(int, raw_input().split())
        ab = a+b
        for prime in primes:
            if prime > ab:
                print prime-ab
                break
Advertisements