Given an array of n integers. Find the minimum positive number to be inserted in array, so that sum of all elements of array becomes prime. If sum is already prime, then return 0.
 
Example 1:
Input:
N=5
arr[] = { 2, 4, 6, 8, 12 }
Output:  5
Explanation: 
The sum of the array is 32 ,we can add
5 to this to make it 37 which is a
prime number .
Example 2:
Input:
N=3
arr[] = { 1, 5, 7 }
Output:  0 
Explanation: 
The sum of the array is 13 
which is already prime. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minNumber() that takes array arr and integer N as input parameters and returns the minimum positive number to be inserted in the array so as to make it's sum a prime number.
 
Expected Time Complexity: O(N log(log N))
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Data structures

Starter code: #User function Template for python3




def minNumber(arr,N):
    # code here


Solutions:
def isprime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	a = sum(arr)
	i = 0
	while True:
		if isprime(a + i):
			return i
			break
		i += 1


def isPrime(N):
	if N < 2:
		return False
	for i in range(2, N // 2 + 1):
		if N % i == 0:
			return False
	return True

def minNumber(arr, N):
	sum1 = sum(arr)
	if isPrime(sum1):
		return 0
	i = 1
	while True:
		if isPrime(sum1 + i):
			return i
		i += 1


import math

def fun(n):
	if n == 0 or n == 1:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	n = sum(arr)
	if fun(n):
		return 0
	else:
		l = n + 1
		while 1:
			if fun(l):
				return abs(l - n)
			l += 1


import math

def is_prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	sum_ = sum(arr)
	if sum_ == 1:
		return 0
	count = 0
	while not is_prime(sum_):
		sum_ += 1
		count += 1
	return count


def minNumber(arr, N):

	def is_prime(n):
		import math
		if n < 2:
			return False
		a = int(math.sqrt(n))
		for i in range(2, a + 1):
			if n % i == 0:
				return False
		return True
	s = sum(arr)
	i = 1
	if is_prime(s) == True:
		return 0
	else:
		while i:
			if is_prime(s + i) == True:
				return i
			else:
				i += 1


def minNumber(arr, N):
	num = sum(arr)
	s = sum(arr)
	while True:
		prime = True
		for i in range(2, num):
			if num % i == 0:
				prime = False
				break
		if prime:
			break
		else:
			num += 1
	return num - s


import math

def minNumber(arr, N):

	def prime(x):
		k = 0
		if x < 2:
			return False
		p = int(math.sqrt(x))
		for i in range(2, p + 1):
			if x % i == 0:
				k = 1
		if k == 1:
			return False
		else:
			return True
	z = sum(arr)
	if prime(z):
		return 0
	else:
		i = 1
		while i:
			if prime(z + i) == True:
				return i
			i = i + 1


import math

def isprime(n):
	s = int(math.sqrt(n))
	if n <= 1:
		return 0
	for i in range(2, s + 1):
		if n % i == 0:
			return 0
	return 1

def minNumber(arr, N):
	sum = 0
	for i in arr:
		sum = sum + i
	if isprime(sum) == 1:
		return 0
	for i in range(1, sum):
		a = sum + i
		if isprime(a) == 1:
			return i


import math

def minNumber(arr, N):

	def prime(n):
		if n == 1 or n == 0:
			return False
		else:
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					return False
					break
			else:
				return True
	s = sum(arr)
	d = 0
	while True:
		if prime(s):
			break
		else:
			s += 1
	return abs(s - sum(arr))


import math

def primes(n):
	if n <= 1:
		return False
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	sum = 0
	for i in range(len(arr)):
		sum = sum + arr[i]
	for i in range(sum):
		if primes(sum + i):
			return i


import math

def prime(N):
	if N < 2:
		return False
	sq = int(math.sqrt(N))
	for i in range(2, sq + 1):
		if N % i == 0:
			return False
	return True

def minNumber(arr, N):
	c = 0
	if prime(sum(arr)):
		return '0'
	else:
		for j in range(1, sum(arr)):
			if prime(sum(arr) + j):
				c = j
				break
		return c


def minNumber(arr, N):
	s = sum(arr)
	while s > 0:
		for i in range(2, int(s ** 0.5) + 1):
			if s % i == 0:
				s += 1
				break
		else:
			return 0 if s == sum(arr) else s - sum(arr)


def isPrime(n):
	a = int(pow(n, 0.5))
	c = 0
	for i in range(1, a + 1):
		if n % i == 0:
			c += 1
	if c == 1:
		return True
	return False

def minNumber(l, N):
	s = sum(l)
	i = 0
	if isPrime(s) == False:
		temp = s
		x = True
		while x:
			s = s + i
			if isPrime(s) == True:
				return i
			i += 1
			s = temp
	return i


def minNumber(arr, N):
	s = sum(arr)
	if isPrime(s):
		return 0
	else:
		i = 1
		while True:
			if isPrime(s + i):
				return i
			i += 1

def isPrime(n):
	if n < 2:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True


import math

def minNumber(arr, N):

	def isPrime(N):
		c = 0
		if N < 2:
			return False
		s = int(math.sqrt(N))
		for i in range(2, s + 1):
			if N % i == 0:
				c = c + 1
		if c == 0:
			return True
		else:
			return False
	k = sum(arr)
	a = k
	if isPrime(k) == True:
		return 0
	else:
		while k:
			if isPrime(k) == True:
				break
			k = k + 1
	j = k - a
	return j


import math

def is_prime(N):
	if N < 2:
		return 0
	else:
		s = int(math.sqrt(N) + 1)
		for i in range(2, s):
			if N % i == 0:
				return 0
		return 1

def findPrime(n):
	num = n + 1
	while num:
		if is_prime(num):
			return num
		num += 1
	return 0

def minNumber(arr, N):
	s = 0
	for i in range(0, len(arr)):
		s += arr[i]
	if is_prime(s):
		return 0
	num = findPrime(s)
	return num - s


import math

def is_prime(n):
	if n < 2:
		return False
	s = int(math.sqrt(n))
	for i in range(2, s + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	c = 0
	t = 0
	for i in arr:
		c += i
	if is_prime(c) == True:
		return 0
	else:
		for j in range(1, max(arr)):
			c += 1
			t += 1
			if is_prime(c) == True:
				break
	return t


import math

def prime(n):
	if n < 2:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	i = sum(arr)
	while i:
		if prime(i):
			j = i
			break
		i += 1
	return j - sum(arr)


from math import sqrt

def prime(a):
	if a < 2:
		return 0
	for i in range(2, int(sqrt(a)) + 1):
		if a % i == 0:
			return 0
	return 1

def minNumber(arr, N):
	if prime(sum(arr)) == 1:
		return 0
	else:
		for i in range(1, 100):
			if prime(sum(arr) + i) == 1:
				return i
				break


import math

def p(k):
	c = 0
	for i in range(2, int(math.sqrt(k) + 1)):
		if k % i == 0:
			c += 1
	if c != 0 or k == 1:
		return 1
	else:
		return 0

def minNumber(arr, n):
	s = sum(arr)
	h = 0
	while p(s):
		h = h + 1
		s = s + 1
	return h


import math

def minNumber(arr, N):

	def isPrime(N):
		if N <= 1:
			return False
		s = int(math.sqrt(N))
		for i in range(2, s + 1):
			if N % i == 0:
				return False
		return True
	b = sum(arr)
	if isPrime(b):
		return 0
	c = b + 1
	while isPrime(c) == False:
		c += 1
	return c - b


import math

def minNumber(arr, N):
	s = sum(arr)

	def prime(r):
		f = 0
		if r == 1:
			f = 1
		for i in range(2, int(math.sqrt(r)) + 1):
			if r % i == 0:
				f = 1
				break
		return f
	if prime(s) == 0:
		return 0
	else:
		for i in range(s + 1, 9999999):
			if prime(i) == 0:
				a = i
				break
		return a - s


import math

def isprime(n):
	if n == 1:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	c = 0
	x = 0
	for i in arr:
		x += i
	if isprime(x) == True:
		return '0'
	else:
		while isprime(x) == False:
			x += 1
			c += 1
	return c


import math

def ip(n):
	c = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			c = c + 1
	if c != 0 or n == 1:
		return False
	else:
		return True

def minNumber(arr, N):
	k = sum(arr)
	for i in range(0, k * N):
		if ip(k + i) == True:
			return i


def minNumber(arr, N):

	def isprime(N):
		if N == 1:
			return 0
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				return 0
		return 1
	a = sum(arr)
	if isprime(a):
		return 0
	else:
		i = 1
		while i:
			if isprime(a + i):
				return i
			i += 1


import math

def minNumber(arr, N):

	def isprime(N):
		if N == 0 or N == 1:
			return 0
		for i in range(2, int(math.sqrt(N)) + 1):
			if N % i == 0:
				return 0
		return 1
	if isprime(sum(arr)) == 1:
		return 0
	else:
		i = sum(arr)
		c = 0
		while True:
			if isprime(i) == 1:
				return i - sum(arr)
			else:
				i += 1


import math

def minNumber(arr, N):

	def prime(n):
		if n == 1:
			return False
		c = int(math.sqrt(n))
		for i in range(2, c + 1):
			if n % i == 0:
				return False
		return True
	s = sum(arr)
	if prime(s):
		return 0
	else:
		for i in range(1, max(arr)):
			if prime(s + i):
				return i


def minNumber(arr, N):

	def prime(n):
		c = 0
		if n == 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				c = 1
				break
		if c == 0:
			return True
		else:
			return False
	v = sum(arr)
	if prime(v):
		return '0'
	else:
		i = 1
		while i:
			if prime(v + i) == True:
				return i
			i += 1


import math as m

def minNumber(arr, N):

	def prime(n):
		if n <= 1:
			return False
		for i in range(2, round(m.sqrt(n)) + 1):
			if n % i == 0:
				return False
		return True
	if prime(sum(arr)):
		return 0
	else:
		i = 1
		while True:
			if prime(sum(arr) + i):
				return i
			i += 1


import math

def minNumber(arr, N):
	total_sum = sum(arr)
	for i in range(0, 10 ** 5):
		total = total_sum + i
		if is_prime(total):
			return i

def is_prime(num):
	if num == 1:
		return False
	sqa = int(math.sqrt(num))
	for i in range(2, sqa + 1):
		if num % i == 0:
			return False
	return True


def minNumber(arr, N):
	s = sum(arr)
	d = s
	i = 1
	while i < s - 1:
		i = i + 1
		if s % i == 0:
			s = s + 1
			i = 1
	return s - d


isPrime = [1] * 100005

def sieveOfEratostheneses():
	isPrime[1] = False
	i = 2
	while i * i < 100005:
		if isPrime[i]:
			j = 2 * i
			while j < 100005:
				isPrime[j] = False
				j += i
		i += 1
	return

def findPrime(n):
	num = n + 1
	while num:
		if isPrime[num]:
			return num
		num += 1
	return 0

def minNumber(arr, N):
	sieveOfEratostheneses()
	s = sum(arr)
	if isPrime[s]:
		return 0
	n = findPrime(s)
	return n - s


def minNumber(arr, N):
	s = sum(arr)

	def isPrime(n):
		if n < 2:
			return False
		for i in range(2, n, 1):
			if n % i == 0:
				return False
		return True
	m = 0
	if isPrime(s) == False:
		while isPrime(s) == False:
			s += 1
			m += 1
	return m


from math import sqrt
from bisect import bisect_left
primes = [2, 3]

def minNumber(arr, N):
	summa = sum(arr)
	while summa > primes[-1]:
		i = primes[-1]
		flag = False
		while True:
			i += 2
			flag = True
			for item in primes:
				if i % item == 0:
					flag = False
					break
			if flag:
				primes.append(i)
				break
	i = bisect_left(primes, summa)
	return primes[i] - summa


def check_prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

def next_arr(n):
	while True:
		if check_prime(n):
			return n
		n = n + 1

def minNumber(arr, N):
	sums = sum(arr)
	if check_prime(sums):
		return 0
	else:
		return next_arr(sums) - sums


def minNumber(arr, N):
	rec = sum(arr)

	def isPrime(n):
		if n == 0 or n == 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True
	ans = 0
	while not isPrime(rec):
		rec += 1
		ans += 1
	return ans


import math

def primes():
	n = int(100000.0)
	pl = [True] * (n + 1)
	pl[0] = pl[1] = False
	lim = int(math.sqrt(n)) + 1
	for i in range(2, lim):
		for j in range(i * i, n + 1, i):
			if pl[i]:
				pl[j] = False
	res = []
	for i in range(2, n + 1):
		if pl[i]:
			res.append(i)
	return res

def bsc(arr, k):
	n = len(arr)
	(l, h, ans) = (0, n - 1, -1)
	while l <= h:
		m = (l + h) // 2
		if arr[m] < k:
			l = m + 1
		else:
			ans = arr[m]
			h = m - 1
	return ans

def isPrime(n):
	if n == 1:
		return False
	else:
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			if n % i == 0:
				return False
		return True
pl = primes()

def minNumber(arr, N):
	s = sum(arr)
	if isPrime(s):
		return 0
	return bsc(pl, s) - s


import math

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def nextPrime(N):
	if N <= 1:
		return 2
	prime = N
	found = False
	while not found:
		prime = prime + 1
		if isPrime(prime) == True:
			found = True
	return prime

def minNumber(arr, N):
	if isPrime(sum(arr)):
		return 0
	return nextPrime(sum(arr)) - sum(arr)


def isPrime(k):
	if k > 1:
		for i in range(2, k // 2 + 1):
			if k % i == 0:
				return False
				break
		return True
	else:
		return False

def minNumber(arr, N):
	s = 0
	m = 0
	for i in arr:
		s += i
	while True:
		if isPrime(s):
			return m
		else:
			m += 1
			s += 1


def minNumber(arr, N):
	s = 0
	for i in arr:
		s += i

	def isprime(n):
		if n < 2:
			return False
		if n < 4:
			return True
		if not n % 2 or not n % 3:
			return False
		i = 5
		while i * i <= n:
			if not n % i:
				return False
			i += (i + 3) % 6
		return True

	def lpge(n):
		if n <= 2:
			return 2
		if isprime(n):
			return n
		if not n % 2:
			n += 1
		while not isprime(n):
			n += 2
		return n
	return lpge(s) - s


def minNumber(arr, N):

	def isprime(n):
		count = 0
		for i in range(2, n // 2 + 1):
			if n % i == 0:
				return False
		return True
	sum = 0
	for i in arr:
		sum += i
	z = sum
	if isprime(sum):
		return 0
	while True:
		z += 1
		if isprime(z):
			return z - sum


def isprime(n):
	if n <= 1:
		return 0
	for i in range(2, n):
		if n % i == 0:
			return 0
	return 1

def minNumber(arr, N):
	sum = 0
	for i in range(N):
		sum = sum + arr[i]
	if isprime(sum):
		return 0
	for i in range(1, sum):
		if isprime(sum + i):
			return i


from math import sqrt

def isprime(x):
	if x <= 1:
		return 0
	if x <= 3:
		return 1
	if x % 2 == 0 or x % 3 == 0:
		return 0
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return 0
	return 1

def minNumber(arr, N):
	sm = sum(arr)
	if isprime(sm):
		return 0
	else:
		for i in range(1, sm // 2 + 1):
			if isprime(sm + i):
				return i


def minNumber(arr, N):

	def isprime(n):
		if n <= 1:
			return False
		for i in range(2, n):
			if n % i == 0:
				return False
		return True
	sum = 0
	for i in range(len(arr)):
		sum += arr[i]
	if isprime(sum):
		return 0
	else:
		for i in range(1, sum):
			if isprime(i + sum):
				break
		return i


def minNumber(arr, N):

	def isPrime(num):
		for i in range(2, num // 2):
			if num % i == 0:
				return False
		return True
	if isPrime(sum(arr)):
		return 0
	else:
		add = 1
		while True:
			if isPrime(sum(arr) + add):
				return add
			else:
				add += 1


def minNumber(arr, N):
	a = sum(arr)
	n = sum(arr)
	while True:
		for i in range(2, n):
			if n % i == 0:
				n += 1
				break
		else:
			return n - a
			break


def minNumber(arr, N):

	def prime(n):
		for i in range(2, int(n / 2)):
			if n % i == 0:
				return False
		return True
	s = sum(arr)
	if prime(s):
		return 0
	else:
		for i in range(1, 100):
			s += i
			if prime(s):
				return i
				break
			s -= i


def nextprime(s):
	for i in range(s + 1, 100000):
		for j in range(2, i):
			if i % j == 0:
				break
		else:
			return i

def isprime(s):
	for i in range(2, s // 2):
		if s % i == 0:
			return 0
	else:
		return 1

def minNumber(arr, N):
	s = sum(arr)
	t = nextprime(s)
	if isprime(s):
		return 0
	else:
		x = t - s
		return x


def minNumber(arr, n):
	su = sum(arr)
	j = su
	while True:
		temp = True
		for i in range(2, su):
			if j % i == 0:
				temp = False
				break
		if temp == True and j >= su:
			break
		j += 1
	return j - su


def sieve():
	arr = [True] * 100002
	arr[0] = arr[1] = False
	for i in range(2, 100002):
		j = 2 * i
		while j < 100002:
			arr[j] = 0
			j = j + i
	return arr

def minNumber(arr, N):
	result = sieve()
	sum = 0
	for i in range(N):
		sum += arr[i]
	if result[sum] == True:
		return 0
	ans = 0
	for i in range(10000 + 1):
		ans = sum + i
		if result[ans] == True:
			return i
		ans = 0


def minNumber(arr, N):
	import math

	def is_prime(n: int) -> bool:
		if n < 2:
			return False
		else:
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
	result = 0
	for i in range(N):
		result += arr[i]
	number = 0
	while True:
		current = result + number
		if is_prime(current):
			return number
		number += 1


def minNumber(arr, N):

	def is_prime(n):
		if n < 2:
			return False
		i = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i += 1
		return True
	s = sum(arr)
	if is_prime(s):
		return 0
	num = 1
	s += 1
	while True:
		if is_prime(s):
			return num
		num += 1
		s += 1


import math

def minNumber(arr, N):
	s = 0
	for i in arr:
		s += i
	for i in range(s):
		if prime(s + i):
			return i

def prime(n):
	if n == 2 or n == 3:
		return 1
	elif n <= 1 or n % 2 == 0 or n % 3 == 0:
		return 0
	for i in range(5, int(math.sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return 0
	return 1


def minNumber(arr, N):
	j = sum(arr)
	while True:
		temp = True
		for k in range(2, j):
			if j % k == 0:
				temp = False
				break
		if temp and j >= sum(arr):
			break
		j += 1
	return j - sum(arr)


import math

def minNumber(arr, N):
	sm = sum(arr)
	j = sm
	while True:
		temp = True
		for k in range(2, int(math.sqrt(j)) + 1):
			if j % k == 0:
				temp = False
				break
		if temp and j >= sm:
			break
		j += 1
	return j - sm


import math

def minNumber(arr, N):

	def isPrime(num):
		for i in range(2, int(math.sqrt(num)) + 2):
			if num % i == 0:
				return 0
		return 1
	sum_arr = sum(arr)
	num = 0
	while True:
		if isPrime(sum_arr + num):
			return num
		num += 1


def minNumber(arr, N):

	def isprime(n):
		if n <= 1:
			return False
		elif n == 2 or n == 3:
			return True
		else:
			for i in range(2, n // 2 + 1):
				if n % i == 0:
					return False
		return True
	f = sum(arr)
	if isprime(f):
		return 0
	else:
		(t, i) = (0, 1)
		while True:
			t = i + f
			if isprime(t):
				return i
			else:
				t -= i
			i += 1


def rec(n):
	for i in range(2, int(n ** 0.5) + 2):
		if n % i == 0:
			prime = 0
			break
		else:
			prime = 1
	if prime == 1:
		return n
	else:
		return rec(n + 1)

def minNumber(arr, N):
	sum = 0
	for i in arr:
		sum += i
	a = rec(sum)
	return a - sum


def minNumber(arr, N):
	k = sum(arr)
	m = []
	for i in range(2, int(k ** (1 / 2)) + 1):
		if k % i == 0:
			m.append(i)
			break
	if len(m) == 0:
		return 0
	else:
		for i in range(1, k):
			s = k + i
			t = []
			for j in range(2, s):
				if s % j == 0:
					t.append(s)
					break
			if len(t) == 0:
				return i


def minNumber(arr, N):

	def isPrime(num):
		if num < 2:
			return 0
		for i in range(2, int(num ** 0.5) + 1):
			if num % i == 0:
				return 0
		return 1
	sumarr = 0
	for i in range(len(arr)):
		sumarr += arr[i]
	if isPrime(sumarr) == 1:
		return 0
	for i in range(1, sumarr):
		if isPrime(i + sumarr) == 1:
			return i


import math

def isPrime(num):
	for x in range(2, int(math.sqrt(num)) + 1):
		if num % x == 0:
			return False
	return True

def minNumber(arr, N):
	s = sum(arr)
	i = 0
	while not isPrime(s):
		i += 1
		s += 1
	return i


l = []
import math

def isPrime(n):
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True

def minNumber(arr, N):
	s = sum(arr)
	for i in range(s, s * s + s):
		if isPrime(i):
			return i - s


def isPrime(num):
	for i in range(2, num):
		if num % i == 0:
			return False
	return True

def minNumber(arr, N):
	sumArr = sum(arr)
	flag = False
	val = 0
	sum1 = sum(arr)
	while not flag:
		if isPrime(sum1):
			flag = True
		else:
			sum1 += 1
			val += 1
	return val


def primenum(sum1):
	for i in range(2, sum1):
		if sum1 % i == 0:
			return False
	return True

def minNumber(arr, N):
	flag = False
	sum1 = 0
	value = 0
	for i in range(N):
		sum1 = sum1 + arr[i]
	while not flag:
		if primenum(sum1):
			flag = True
		else:
			sum1 += 1
			value += 1
	return value