You are given the head of a linked list. You have to replace all the values of the nodes with the nearest prime number. If more than one prime number exists at an equal distance, choose the smallest one.
Example 1:
Input:
2 → 6 → 10
Output:
2 → 5 → 11
Explanation:
The nearest prime of 2 is 2 itself.
The nearest primes of 6 are 5 and 7,
since 5 is smaller so, 5 will be chosen.
The nearest prime of 10 is 11.
 
Example 2:
Input:
1 → 15 → 20
Output:
2 → 13 → 19
Explanation:
The nearest prime of 1 is 2.
The nearest primes of 15 are 13 and 17,
since 13 is smaller so, 13 will be chosen.
The nearest prime of 20 is 19.
Your Task:
The task is to complete the function primeList() which contains a reference to the head as the only argument. This function should return the head of the modified linked list.
Expected Time Complexity: O(number of nodes * sqrt(value of node)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ Number of Nodes ≤ 10^{4}
1 ≤ Value on Node ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics

Starter code: from typing import Optional



"""



Definition for singly Link List Node

class Node:

    def __init__(self,x):

        self.data=x

        self.next=None



You can also use the following for printing the link list.

printList(node)

"""



class Solution:

    def primeList(self, head : Optional['Node']) -> Optional['Node']:

        # code here

        



Solutions:
from typing import Optional
import math

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		def newprime(n):
			i = n
			j = n
			while not (isprime(i) or isprime(j)):
				i -= 1
				j += 1
			if isprime(i):
				return i
			return j

		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
		temp = head
		while temp:
			temp.data = newprime(temp.data)
			temp = temp.next
		return head


from typing import Optional
from math import sqrt

class Solution:
	MAX_VALUE = 10 ** 4

	def sieve(self, n):
		n1 = n + 1
		s = [True] * n1
		s[0] = s[1] = False
		for i in range(int(sqrt(n1)) + 1):
			if not s[i]:
				continue
			for j in range(i * i, n1, i):
				s[j] = False
		return s

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

	def nearest_prime(self, n):
		if self.is_prime(n):
			return n
		(left, right) = (n - 1, n + 1)
		while True:
			if self.is_prime(left):
				return left
			if self.is_prime(right):
				return right
			(left, right) = (left - 1, right + 1)

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		current_prime = 2
		node = head
		while node:
			node.data = self.nearest_prime(node.data)
			node = node.next
		return head


from typing import Optional
import sys
sys.setrecursionlimit(100000)

class Solution:

	def find_binary_search_rightmost(self, target_list, left, right, target):
		while left < right:
			mid = (left + right) // 2
			if target_list[mid] > target:
				right = mid
			else:
				left = mid + 1
		if right - 1 == -1:
			return 0
		else:
			return right - 1

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		prime_list = list()
		prime_list = self.findPrime()
		number_of_primes = len(prime_list) - 1
		dp = [-1] * int(100000.0 + 1)
		dp2 = [-1] * int(100000.0 + 1)
		self.change_value(head, prime_list, number_of_primes, dp, dp2)
		return head

	def change_value(self, head, prime_list, number_of_primes, dp, dp2):
		if head is None:
			return
		if dp[head.data] == -1:
			index = self.find_binary_search_rightmost(prime_list, 0, number_of_primes, head.data)
			dp[head.data] = index
		else:
			index = dp[head.data]
		if dp2[head.data] == -1:
			if index >= 0 and index < number_of_primes:
				if abs(prime_list[index] - head.data) <= abs(prime_list[index + 1] - head.data):
					dp2[head.data] = prime_list[index]
					head.data = dp2[head.data]
				else:
					dp2[head.data] = prime_list[index + 1]
					head.data = dp2[head.data]
			elif abs(prime_list[index - 1] - head.data) <= abs(prime_list[index] - head.data):
				dp2[head.data] = prime_list[index - 1]
				head.data = dp2[head.data]
			else:
				dp2[head.data] = prime_list[index]
				head.data = dp2[head.data]
		else:
			head.data = dp2[head.data]
		self.change_value(head.next, prime_list, number_of_primes, dp, dp2)

	def findPrime(self):
		prime_list = list()
		max = int(20000)
		is_prime = [True] * max
		is_prime[0] = False
		is_prime[1] = False
		for i in range(1, max):
			if is_prime[i]:
				prime_list.append(i)
				for j in range(2, max):
					if i * j >= max:
						break
					else:
						is_prime[i * j] = False
		return prime_list


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		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
		ans = []
		while head:
			cur = head.data
			if isprime(cur):
				ans.append(cur)
				head = head.next
			else:
				prev = cur - 1
				nex = cur + 1
				while not isprime(prev) and (not isprime(nex)):
					prev -= 1
					nex += 1
				if isprime(prev):
					ans.append(prev)
				else:
					ans.append(nex)
				head = head.next
		for i in ans:
			print(i, end=' ')


from typing import Optional
import bisect
import math
MAX = 100005
prime_numbers = []

def sieve_of_eratosthenes():
	prime = [True] * (MAX + 1)
	for p in range(2, int(math.sqrt(MAX)) + 1):
		if prime[p]:
			for i in range(p * p, MAX + 1, p):
				prime[i] = False
	for i in range(2, MAX + 1):
		if prime[i]:
			prime_numbers.append(i)

def closest_prime(number):
	if number == 1:
		return 2
	else:
		index = bisect.bisect_left(prime_numbers, number)
		if prime_numbers[index] == number or prime_numbers[index - 1] == number:
			return number
		elif abs(prime_numbers[index] - number) < abs(prime_numbers[index - 1] - number):
			return prime_numbers[index]
		else:
			return prime_numbers[index - 1]

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		sieve_of_eratosthenes()
		tmp = head
		while head:
			head.data = closest_prime(head.data)
			head = head.next
		return tmp


from typing import Optional
from math import sqrt

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		def prime(x):
			if x == 1:
				return False
			for j in range(2, int(sqrt(x)) + 1):
				if x % j == 0:
					return False
			return True

		def find(n):
			flag = True
			i = 1
			while flag:
				(x1, x2) = (n - i, n + i)
				if prime(x1):
					flag = True
					return x1
				elif prime(x2):
					flag = True
					return x2
				i += 1
			return 0
		temp = head
		while temp:
			if not prime(temp.data):
				if temp.data == 1:
					temp.data = 2
				else:
					val = find(temp.data)
					temp.data = val
			temp = temp.next
		return head


from typing import Optional
import math
import bisect

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

def close(n1, n2, x):
	if x - n1 == n2 - x:
		return n1
	if x - n1 < n2 - x:
		return n1
	return n2

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		n = 0
		while temp != None:
			n = max(n, temp.data)
			temp = temp.next
		lis = []
		for i in range(2, n + 100):
			if check(i):
				lis.append(i)
		cur = head
		while cur != None:
			idx = bisect.bisect(lis, cur.data)
			x = close(lis[idx - 1], lis[idx], cur.data)
			if cur.data != 1:
				cur.data = x
			else:
				cur.data = 2
			cur = cur.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

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

		def findNextPrimeLower(num):
			if num < 3:
				return 2
			for i in range(num - 1, int(num ** 0.5 // 1), -1):
				if isPrime(i):
					return i

		def findNextPrimeHigher(num, lower):
			for i in range(num + 1, num + lower):
				if isPrime(i):
					return i
			return -1
		node = head
		while node:
			if not isPrime(node.data):
				lower = findNextPrimeLower(node.data)
				higher = findNextPrimeHigher(node.data, lower)
				if higher == -1:
					node.data = lower
				elif abs(node.data - lower) > abs(node.data - higher):
					node.data = higher
				else:
					node.data = lower
			node = node.next
		return head


from typing import Optional
import math

class Solution:

	def isPrime(self, n):
		if n == 2:
			return True
		else:
			x = 2
			while x <= math.sqrt(n):
				if n % x == 0:
					return False
				x += 1
			return True

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		if head == None:
			return
		current = head
		leftdist = 0
		rightdist = 0
		while current != None:
			value = current.data
			if value == 1:
				current.data = 2
				continue
			leftdist = rightdist = value
			while self.isPrime(leftdist) == False:
				leftdist -= 1
			while self.isPrime(rightdist) == False:
				rightdist += 1
			if value - leftdist <= rightdist - value:
				value = leftdist
			else:
				value = rightdist
			current.data = value
			current = current.next
		return head


from typing import Optional
from math import sqrt, ceil, floor

class Solution:

	def isPrime(self, num):
		for i in range(2, ceil(sqrt(num)) + 1):
			if num % i == 0:
				return False
		return True

	def nearPrime(self, N):
		if self.isPrime(N):
			return N
		pprime = 2
		for i in range(N - 1, 1, -1):
			if self.isPrime(i):
				pprime = i
				break
		nprime = float('inf')
		for i in range(N, N + pprime + 1):
			if self.isPrime(i):
				nprime = i
				break
		if N - pprime > nprime - N:
			return nprime
		return pprime

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp:
			if temp.data == 0:
				temp = temp.next
				continue
			if temp.data == 1:
				temp.data = 2
				temp = temp.next
				continue
			temp.data = self.nearPrime(temp.data)
			temp = temp.next
		return head


from typing import Optional

class Solution:

	def is_prime(self, 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 find_nearest_prime(self, n):
		if self.is_prime(n):
			return n
		else:
			left = n - 1
			right = n + 1
			while True:
				if self.is_prime(left):
					return left
				elif self.is_prime(right):
					return right
				left -= 1
				right += 1

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		node = head
		while node:
			node.data = self.find_nearest_prime(node.data)
			node = node.next
		return head


from typing import Optional

class Solution:

	def checkPrime(self, num):
		if num % 2 == 0:
			return False
		for n in range(3, round(num ** 0.5 + 1)):
			if num % n == 0:
				return False
		return True

	def findClosestPrime(self, num):
		n = 1 if num % 2 == 0 else 2
		if self.checkPrime(num):
			return num
		while num - n >= 3:
			if self.checkPrime(num - n):
				return num - n
			if self.checkPrime(num + n):
				return num + n
			n += 2

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr:
			if curr.data >= 4:
				curr.data = self.findClosestPrime(curr.data)
			elif curr.data == 1:
				curr.data = 2
			curr = curr.next
		return head


from typing import Optional
import math

class Solution:

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

	def beforePrime(self, num):
		while self.checkPrime(num) == False:
			num = num - 1
		return num

	def afterPrime(self, num):
		while self.checkPrime(num) == False:
			num = num + 1
		return num

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp != None:
			if temp.data == 1:
				temp.data = 2
			elif self.checkPrime(temp.data) == False:
				first = self.beforePrime(temp.data)
				second = self.afterPrime(temp.data)
				if abs(first - temp.data) <= abs(second - temp.data):
					temp.data = first
				else:
					temp.data = second
			temp = temp.next
		return head


from typing import Optional
import math

class Solution:

	def isPrime(self, num):
		if num == 2:
			return True
		else:
			k = 2
			while k <= math.sqrt(num):
				if num % k == 0:
					return False
				k += 1
			return True

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		(n1, n2) = (0, 0)
		while temp != None:
			data = temp.data
			if data == 1:
				temp.data = 2
				continue
			n1 = n2 = data
			while self.isPrime(n2) == False:
				n2 += 1
			while self.isPrime(n1) == False:
				n1 -= 1
			if data - n1 <= n2 - data:
				data = n1
			else:
				data = n2
			temp.data = data
			temp = temp.next
		return head


from typing import Optional
import math

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		dict1 = {}

		def isprime(num):
			if num == 2:
				return True
			else:
				k = 2
				while k <= math.sqrt(num):
					if num % k == 0:
						return False
					k += 1
				return True
		ptr = head
		while ptr != None:
			if ptr.data in dict1:
				ptr.data = dict1[ptr.data]
				ptr = ptr.next
			elif ptr.data == 1:
				ptr.data = 2
				ptr = ptr.next
			else:
				val = ptr.data
				a = 0
				while not isprime(val):
					val -= 1
				a = val
				val = ptr.data
				while not isprime(val):
					val += 1
				if abs(ptr.data - a) <= abs(ptr.data - val):
					ptr.data = a
					dict1[ptr.data] = a
				else:
					dict1[ptr.data] = val
					ptr.data = val
				ptr = ptr.next
		return head


from typing import Optional
import math as mt

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

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

		def nprime(n):
			a = b = n
			pr1 = pr2 = 0
			if n == 1:
				return 2
			if is_prime(n):
				return n
			else:
				while not is_prime(a):
					a = a + 1
				pr1 = a
				while not is_prime(b) and b >= 1:
					b = b - 1
				pr2 = b
			(d, f) = (pr1 - n, n - pr2)
			if d >= f:
				return pr2
			else:
				return pr1

		def traverse(head):
			p = head
			while p:
				p.data = nprime(p.data)
				p = p.next
			return head
		return traverse(head)


from typing import Optional

class Solution:

	def printmap(self, isPrime, N):
		for i in range(1, N + 1):
			print(i, isPrime[i])

	def SeiveOfErathosthenes(self, isPrime, N):
		for i in range(2, N):
			if i ** 2 > N:
				break
			for j in range(i ** 2, N + 1, i):
				if i != j and j % i == 0:
					isPrime[j] = False

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		isPrime = {}
		for i in range(10010):
			isPrime[i] = True
		isPrime[1] = False
		self.SeiveOfErathosthenes(isPrime, 10010)
		left = -1
		for i in range(1, 10010):
			if isPrime[i]:
				left = i
			isPrime[i] = [left, -1]
		right = -1
		for i in range(10010 - 1, 0, -1):
			if isPrime[i][0] == i:
				right = i
			isPrime[i][1] = right
		root = head
		while head:
			(x, y) = isPrime[head.data]
			if x == -1:
				head.data = y
			elif y == -1:
				head.data = x
			elif head.data - x < y - head.data:
				head.data = x
			elif head.data - x == y - head.data:
				head.data = x
			else:
				head.data = y
			head = head.next
		return root


from typing import Optional
import math

class Solution:

	def __init__(self):
		self.pl = self.primes()

	def primes(self):
		n = int(10000.0 + 10)
		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 bsf(self, arr, k):
		n = len(arr)
		(l, h, idx) = (0, n - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] > k:
				h = m - 1
			else:
				idx = m
				l = m + 1
		return idx

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

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp != None:
			if temp.data not in self.pl:
				x = self.bsf(self.pl, temp.data)
				y = self.bsc(self.pl, temp.data)
				if x == -1 and y != -1:
					temp.data = self.pl[y]
				elif y == -1 and x != -1:
					temp.data = self.pl[x]
				else:
					(t1, t2) = (self.pl[x], self.pl[y])
					if temp.data - t1 <= t2 - temp.data:
						temp.data = t1
					else:
						temp.data = t2
			temp = temp.next
		return head


from typing import Optional

class Solution:

	def checkprime(self, num):
		if num == 2 or num == 3:
			return 1
		for i in range(2, int(num ** (1 / 2)) + 1):
			if num % i == 0:
				return 0
		return 1

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		current = head
		while current:
			if current.data == 1:
				current.data = 2
			elif not self.checkprime(current.data):
				list = []
				amount = current.data
				i = 1
				while i > 0:
					if self.checkprime(amount - i):
						list.append(amount - i)
						i = 0
					elif self.checkprime(amount + i):
						list.append(amount + i)
						i = 0
					else:
						i += 1
				current.data = list[0]
			current = current.next
		return head


from typing import Optional
N = int(10 ** 4.2) + 1
prime = [1 for i in range(N)]
for i in range(2, N):
	if prime[i] == 1:
		for j in range(i * i, N, i):
			prime[j] = 0
lis = []
for i in range(2, N):
	if prime[i]:
		lis.append(i)
from bisect import bisect_left

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		ans = head
		while ans:
			data = ans.data
			ind = bisect_left(lis, data)
			if lis[ind] == data:
				ans = ans.next
				continue
			if ind == 0:
				ans.data = 2
			elif ans.data - lis[ind - 1] <= lis[ind] - ans.data:
				ans.data = lis[ind - 1]
			else:
				ans.data = lis[ind]
			ans = ans.next
		return head


from typing import Optional

class Solution:

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

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp:
			if temp.data == 1:
				temp.data = 2
			else:
				num = temp.data
				num1 = temp.data
				num2 = temp.data
				while not self.isPrime(num1):
					num1 -= 1
				while not self.isPrime(num2):
					num2 += 1
				if num - num1 <= num2 - num:
					temp.data = num1
				else:
					temp.data = num2
			temp = temp.next
		return head


from typing import Optional

class Node:

	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

class Solution:

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

	def primeList(self, head: Optional[Node]) -> Optional[Node]:
		current = head
		while current:
			i = 0
			while not self.is_prime(current.data - i) and current.data - i >= 2:
				i += 1
			lower_prime = current.data - i if self.is_prime(current.data - i) else float('inf')
			j = 0
			while not self.is_prime(current.data + j):
				j += 1
			higher_prime = current.data + j
			if abs(current.data - lower_prime) <= abs(higher_prime - current.data):
				nearest_prime = lower_prime
			else:
				nearest_prime = higher_prime
			current.data = nearest_prime
			current = current.next
		return head


from typing import Optional

class Solution:

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

	def replace(self, n):
		eq = n
		temp = n + 1
		n -= 1
		(a, b) = (None, None)
		while n > 1:
			if self.isprime(n):
				a = n
				break
			n -= 1
		while self.isprime(temp) == False:
			temp += 1
		b = temp
		if a == None:
			return b
		elif b == None:
			return a
		elif eq - a > b - eq:
			return b
		elif eq - a <= b - eq:
			return a

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while head != None:
			if not self.isprime(head.data):
				head.data = self.replace(head.data)
			head = head.next
		return temp


from typing import Optional
import math

class Solution:

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

	def nearPrime(self, n):
		if n == 1:
			return 2
		for i in range(n, 1, -1):
			if self.isPrime(i):
				p1 = i
				break
		for i in range(n, n * n, 1):
			if self.isPrime(i):
				p2 = i
				break
		if abs(p1 - n) < abs(p2 - n):
			return p1
		elif abs(p2 - n) < abs(p1 - n):
			return p2
		else:
			return min(p1, p2)

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		p = head
		while p:
			if not self.isPrime(p.data):
				p.data = self.nearPrime(p.data)
			p = p.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		dummyhead = Node(-1)
		temp = dummyhead

		def isprime(x):
			if x == 1:
				return 0
			elif x == 0:
				return 0
			for y in range(2, int(x ** 0.5) + 1):
				if x % y == 0:
					return 0
			return 1
		while head != None:
			i = 0
			while 1:
				if isprime(abs(head.data - i)):
					newNode = Node(abs(head.data - i))
					temp.next = newNode
					temp = newNode
					break
				elif isprime(head.data + i):
					newNode = Node(head.data + i)
					temp.next = newNode
					temp = newNode
					break
				i += 1
			head = head.next
		return dummyhead.next


from typing import Optional
from math import sqrt

class Solution:

	def primeCheck(self, num):
		if num <= 1:
			return False
		for i in range(2, int(sqrt(num)) + 1):
			if num % i == 0:
				return False
		return True

	def bs_lower(self, arr, n, x):
		start = 0
		end = n - 1
		lower = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] == x:
				end = mid
			if arr[mid] < x:
				start = mid + 1
				lower = arr[mid]
			if arr[mid] > x:
				end = mid - 1
		return lower

	def bs_upper(self, arr, n, x):
		start = 0
		end = n - 1
		upper = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] == x:
				start = mid + 1
			if arr[mid] < x:
				start = mid + 1
			if arr[mid] > x:
				end = mid - 1
				upper = arr[mid]
		return upper

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		l = []
		for i in range(15000):
			if self.primeCheck(i):
				l.append(i)
		temp = head
		while temp != None:
			num = temp.data
			if temp.data == 1:
				temp.data = 2
				temp = temp.next
				continue
			if self.primeCheck(temp.data) == False:
				(a, b) = (self.bs_lower(l, len(l), temp.data), self.bs_upper(l, len(l), temp.data))
				if abs(num - a) > abs(num - b):
					temp.data = b
				if abs(num - a) < abs(num - b):
					temp.data = a
				if abs(num - a) == abs(num - b):
					temp.data = min(a, b)
			temp = temp.next
		return head


from typing import Optional

def checknearnumber(number, prime):
	if number <= 2:
		return 2
	left = number
	while True:
		if prime[left] == True:
			break
		left -= 1
	right = number
	while True:
		if prime[right] == True:
			break
		right += 1
	if abs(number - left) > abs(number - right):
		return right
	return left

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		prime = [True for _ in range(10500)]
		prime[0] = prime[1] = False
		for i in range(2, 10500):
			if prime[i] == True:
				for j in range(i * i, 10500, i):
					prime[j] = False
		travs = head
		while travs != None:
			x = checknearnumber(travs.data, prime)
			travs.data = x
			travs = travs.next
		return head


from typing import Optional

class Solution:

	def isPrime(self, p):
		if p <= 1:
			return False
		i = 2
		while i * i <= p:
			if p % i == 0:
				return False
			i += 1
		return True

	def getNearestPrime(self, num):
		if self.isPrime(num):
			return num
		(l, r) = (num - 1, num + 1)
		while l >= 0 and (not self.isPrime(l)):
			l -= 1
		while not self.isPrime(r):
			r += 1
		if l < 0:
			return r
		if num - l <= r - num:
			return l
		return r

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp is not None:
			temp.data = self.getNearestPrime(temp.data)
			temp = temp.next
		return head


from typing import Optional
import math

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

def find(value, flg):
	while True:
		if isprime(value - flg):
			return value - flg
		if isprime(value + flg):
			return value + flg
		flg += 2

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		root = head
		while root:
			value = root.data
			if value == 2:
				root = root.next
				continue
			elif value == 1:
				root.data = 2
			elif value % 2 == 0:
				root.data = find(value, 1)
			else:
				root.data = find(value, 0)
			root = root.next
		return head


from typing import Optional
from bisect import *
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009]

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		cur = head
		while cur != None:
			ind = bisect_left(primes, cur.data)
			if ind == 0:
				if primes[0] == cur.data:
					pass
				else:
					cur.data = primes[0]
			else:
				left = ind - 1
				right = ind
				if cur.data == primes[right]:
					pass
				else:
					d1 = cur.data - primes[left]
					d2 = primes[right] - cur.data
					if d1 <= d2:
						cur.data = primes[left]
					else:
						cur.data = primes[right]
			cur = cur.next
		return head


from typing import Optional

class Solution:

	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 primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr != None:
			x = curr.data
			if x == 1:
				curr.data = 2
			else:
				i = 0
				while i < x:
					if Solution.isPrime(abs(i - x)):
						curr.data = abs(i - x)
						break
					elif Solution.isPrime(i + x):
						curr.data = i + x
						break
					i += 1
			curr = curr.next
		return head


from typing import Optional

def isPrime(n):
	if n == 1:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr is not None:
			if isPrime(curr.data):
				curr = curr.next
			else:
				i = curr.data
				j = curr.data
				while not isPrime(i):
					i += 1
				while not isPrime(j):
					j -= 1
				if i - curr.data >= curr.data - j:
					curr.data = j
				else:
					curr.data = i
				curr = curr.next
		return head


from typing import Optional
import bisect
import math

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		a = [1 for i in range(11001)]
		for i in range(2, int(math.sqrt(11001)) + 1):
			for j in range(i, 11001 // i):
				a[i * j] = 0
		prime = [i for i in range(2, 11001) if a[i]]
		cur = head
		while cur:
			if cur.data <= 2:
				cur.data = 2
			else:
				idx = bisect.bisect_right(prime, cur.data)
				if cur.data - prime[idx - 1] <= prime[idx] - cur.data:
					cur.data = prime[idx - 1]
				else:
					cur.data = prime[idx]
			cur = cur.next
		return head


from typing import Optional
import math

class Solution:

	def isPrime(self, 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 primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp != None:
			val = temp.data
			if val == 1:
				temp.data = 2
			prev = temp.data
			while self.isPrime(prev) == False:
				prev -= 1
			ahead = temp.data
			while self.isPrime(ahead) == False:
				ahead += 1
			if val - prev > ahead - val:
				temp.data = ahead
			else:
				temp.data = prev
			temp = temp.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

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

		def getPrime(n):
			i = 0
			if n == 1:
				return 2
			while True:
				if n - i > 1 and isPrime(n - i):
					return n - i
				if isPrime(n + i):
					return n + i
				i += 1
			return -1
		cur = head
		while cur:
			cur.data = getPrime(cur.data)
			cur = cur.next
		return head


from typing import Optional
primes = [True] * (10 ** 4 + 8)
primes[0] = primes[1] = False
for i in range(2, int((10 ** 4 + 8) ** 0.5) + 1):
	if primes[i]:
		for j in range(i * i, 10 ** 4 + 8, i):
			primes[j] = False

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		p = head
		while p:
			x = p.data
			if not primes[x]:
				(l, r) = (x - 1, x + 1)
				while l >= 0 or r <= 10 ** 4 + 7:
					if l >= 0 and primes[l]:
						p.data = l
						break
					elif r <= 10 ** 4 + 7 and primes[r]:
						p.data = r
						break
					l -= 1
					r += 1
			p = p.next
		return head


from typing import Optional
import math

class Solution:

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

	def getprime(self, n):
		prime1 = 0
		prime2 = 0
		if n == 1:
			return 2
		for i in range(n, 1, -1):
			if self.sprime(i):
				prime1 = i
				break
		for i in range(n, n * n):
			if self.sprime(i):
				prime2 = i
				break
		if abs(n - prime1) == abs(n - prime2):
			return prime1
		elif abs(n - prime1) < abs(n - prime2):
			return prime1
		else:
			return prime2

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		ptr = head
		while ptr != None:
			n = ptr.data
			if self.sprime(n):
				ptr.data = n
			else:
				ptr.data = self.getprime(n)
			ptr = ptr.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		n = 10007
		prime = []
		isprime = [True for i in range(10008)]
		isprime[0] = False
		isprime[1] = False
		spf = [0] * 10008
		for i in range(2, n + 1):
			if isprime[i]:
				prime.append(i)
				spf[i] = i
			j = 0
			while j < len(prime) and i * prime[j] <= n and (spf[i] >= prime[j]):
				isprime[i * prime[j]] = False
				spf[i * prime[j]] = prime[j]
				j += 1
		cur = head
		while cur:
			if not isprime[cur.data]:
				if cur.data == 1:
					cur.data = 2
				else:
					lv = cur.data - 1
					rv = cur.data + 1
					while lv >= 1 and (not isprime[lv]):
						lv -= 1
					while rv <= n and (not isprime[rv]):
						rv += 1
					ld = cur.data - lv
					rd = rv - cur.data
					if lv < 1:
						ld = 10008
					if rv > n:
						rd = 10008
					if ld <= rd:
						cur.data = lv
					else:
						cur.data = rv
			cur = cur.next
		return head


from typing import Optional
from math import sqrt

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		cur = head
		while cur is not None:
			if cur.data == 1:
				cur.data = 2
				cur = cur.next
				continue
			x = cur.data
			y = cur.data
			while not self.isPrime(x):
				x -= 1
			while not self.isPrime(y):
				y += 1
			if cur.data - x > y - cur.data:
				cur.data = y
			else:
				cur.data = x
			cur = cur.next
		return head

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


from typing import Optional
from bisect import bisect

class Solution:

	def sieve(self):
		n = 10009
		ss = [True] * (n + 1)
		ss[0] = ss[1] = False
		for i in range(2, int(n ** 0.5) + 3):
			if ss[i]:
				for j in range(2 * i, n + 1, i):
					ss[j] = False
		return ss

	def near(self, a, ss):
		i = bisect(ss, a)
		if i == 0:
			return ss[i]
		else:
			return ss[i - 1] if a - ss[i - 1] <= ss[i] - a else ss[i]

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		ss = [k for (k, v) in enumerate(self.sieve()) if v]
		now = head
		while now:
			now.data = self.near(now.data, ss)
			now = now.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		def is_prime(number):
			if number > 1:
				for num in range(2, int(number ** 0.5) + 1):
					if number % num == 0:
						return False
				return True
			return False

		def nearest_prime(number, distance):
			if is_prime(number - distance):
				return number - distance
			if is_prime(number + distance):
				return number + distance
			return nearest_prime(number, distance + 1)
		node = head
		while node is not None:
			node.data = nearest_prime(node.data, 0)
			node = node.next
		return head


from typing import Optional

class Solution:
	prime_list = [-1] * (100000 + 1)

	def nearest_prime(self, num):
		l = num
		r = num
		while l >= 2 or r <= 100001:
			if self.is_prime(l):
				return l
			if self.is_prime(r):
				return r
			l -= 1
			r += 1
		print('Something went wrong!', num, l, r)

	def is_prime(self, num):
		if self.prime_list[num] != -1:
			return self.prime_list[num] == 1
		if num <= 1:
			return False
		i = 2
		while i * i <= num:
			if num % i == 0:
				self.prime_list[num] = 0
				return False
			i += 1
		self.prime_list[num] = 1
		return True

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		counter = 1
		n = head
		while n:
			n.data = self.nearest_prime(n.data)
			n = n.next
			counter += 1
		return head


from typing import Optional
from math import sqrt, ceil

class Solution:

	def isPrime(self, data):
		if data == 2:
			return True
		n = ceil(sqrt(data))
		count = 0
		for i in range(2, n + 1):
			if data % i == 0 and data % (data // i) == 0:
				count += 2
			elif data % i == 0:
				count += 1
			if count > 1:
				return False
		return True

	def nearestPrime(self, data):
		if data == 1:
			self.minimum = [2]
			return
		data2 = data
		if self.isPrime(data):
			self.minimum.append(data)
			return
		else:
			while not self.isPrime(data):
				data -= 1
			self.minimum.append(data)
			while not self.isPrime(data2):
				data2 += 1
			self.minimum.append(data2)

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp != None:
			self.minimum = []
			data = temp.data
			self.nearestPrime(data)
			if len(self.minimum) == 1:
				temp.data = self.minimum[0]
			else:
				(a, b) = self.minimum
				if data - a < b - data:
					temp.data = a
				elif data - a > b - data:
					temp.data = b
				else:
					temp.data = a
			temp = temp.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		n = head
		while n.next != None:
			self.nearestPrime(n)
			n = n.next
		self.nearestPrime(n)
		return head

	def isPrime(self, n):
		if n <= 1:
			return False
		for i in range(2, n):
			if i * i > n:
				break
			if n % i == 0:
				return False
		return True

	def nearestPrime(self, n):
		i = 1
		while not self.isPrime(n.data) and n.data >= 1:
			if self.isPrime(n.data - i):
				n.data = n.data - i
				break
			if self.isPrime(n.data + i):
				n.data = n.data + i
				break
			i += 1


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr:
			curr.data = self.nearestPrime(curr.data)
			curr = curr.next
		return head

	def nearestPrime(self, x: int) -> int:

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

		def findPrime(num):
			left = num
			right = num
			while True:
				if isPrime(left):
					return left
				elif isPrime(right):
					return right
				left -= 1
				right += 1
		return findPrime(x)


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

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

		def nearest_prime(n):
			if n < 2:
				return 2
			nm = n
			ld = 0
			rd = 0
			while not prime(nm):
				ld += 1
				nm -= 1
			lp = nm
			nm = n
			while not prime(nm):
				rd += 1
				nm += 1
			rp = nm
			return lp if ld <= rd else rp
		cur = head
		while cur:
			if not prime(cur.data):
				cur.data = nearest_prime(cur.data)
			cur = cur.next
		return head


from typing import Optional
import math

class Solution:

	def isprime(self, n):
		if n <= 1:
			return False
		if n == 2 or 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 getnearestprime(self, n):
		if n == 1:
			return 2
		for i in range(n, 1, -1):
			if self.isprime(i):
				prime1 = i
				break
		for i in range(n, n * n):
			if self.isprime(i):
				prime2 = i
				break
		if prime2 - n < n - prime1:
			return prime2
		elif prime2 - n > n - prime1:
			return prime1
		elif prime1 < prime2:
			return prime1
		else:
			return prime2

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr:
			if self.isprime(curr.data) == False:
				new_val = self.getnearestprime(curr.data)
				curr.data = new_val
			curr = curr.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		def sieve(n, arr):
			p = 2
			while p * p <= n:
				if arr[p]:
					for i in range(p * p, n + 1, p):
						arr[i] = False
				p += 1
		n = 10 ** 5
		prime = [True for i in range(n + 1)]
		sieve(n, prime)
		prime[0] = False
		prime[1] = False
		first = head
		while first is not None:
			afterPrime = float('inf')
			beforePrime = float('-inf')
			distance1 = float('inf')
			distance2 = float('inf')
			if not prime[first.data]:
				for i in range(first.data, 0, -1):
					if prime[i]:
						beforePrime = i
						distance1 = abs(first.data - i)
						break
				for i in range(first.data, n + 1):
					if prime[i]:
						afterPrime = i
						distance2 = abs(first.data - i)
						break
				if distance1 == distance2:
					first.data = min(beforePrime, afterPrime)
				elif distance1 < distance2:
					first.data = beforePrime
				else:
					first.data = afterPrime
			first = first.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		if not head:
			return None
		temp = head
		while temp:
			if self.isPrime(temp.data):
				temp = temp.next
			else:
				temp.data = self.getPrime(temp.data)
				temp = temp.next
		return head

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

	def getPrime(self, n):
		if n == 1:
			return 2
		dup_n = n
		(left_direction, right_direction) = (0, 0)
		while dup_n > 1 and (not self.isPrime(dup_n)):
			dup_n -= 1
			left_direction += 1
		dup_n = n
		while dup_n > 1 and (not self.isPrime(dup_n)):
			dup_n += 1
			right_direction += 1
		if left_direction <= right_direction:
			return n - left_direction
		else:
			return n + right_direction


from typing import Optional
import math

class Solution:

	def __init__(self):
		self.primes = self.sieve()

	def sieve(self):
		primes = [True] * int(100000.0 + 1)
		primes[0] = primes[1] = False
		for i in range(2, int(100000.0 + 1)):
			if primes[i]:
				for j in range(i * i, int(100000.0 + 1), i):
					primes[j] = False
		return primes

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		temp = head
		while temp:
			if self.primes[temp.data]:
				temp = temp.next
				continue
			prime1 = prime2 = None
			for i in range(temp.data + 1, int(100000.0 + 1)):
				if self.primes[i]:
					prime2 = i
					break
			for i in range(temp.data - 1, 1, -1):
				if self.primes[i]:
					prime1 = i
					break
			diff1 = diff2 = float('inf')
			if prime1:
				diff1 = abs(prime1 - temp.data)
			if prime2:
				diff2 = abs(prime2 - temp.data)
			if diff1 <= diff2:
				temp.data = prime1
			else:
				temp.data = prime2
			temp = temp.next
		return head


from bisect import bisect_left
from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		node = head
		Cache.sieve(10010)
		while node:
			node.data = Cache.ans[node.data]
			node = node.next
		return head

class Cache:
	ans = []

	@classmethod
	def sieve(cls, n):
		if cls.ans:
			return
		cls.ans = list(range(n + 1))
		cls.ans[0] = 2
		cls.ans[1] = 2
		prime = []
		is_prime = [False, False] + [True] * (n - 1)
		spf = [0] * (n + 1)
		prev = 2
		for i in range(2, n + 1):
			if is_prime[i]:
				prime.append(i)
				spf[i] = i
				for j in range(prev + 1, i):
					if i - j < j - prev:
						cls.ans[j] = i
					else:
						cls.ans[j] = prev
				prev = i
			for p in prime:
				if i * p > n or p > spf[i]:
					break
				is_prime[i * p] = False
				spf[i * p] = p


from typing import Optional
import math

class Solution:

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

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		if head == None:
			return None
		temp = head
		while temp != None:
			if temp.data == 1:
				temp.data = 2
				temp = temp.next
			elif self.isPrime(temp.data):
				temp = temp.next
			else:
				i = temp.data - 1
				j = temp.data + 1
				while not self.isPrime(temp.data):
					if self.isPrime(i):
						temp.data = i
					elif self.isPrime(j):
						temp.data = j
					i = i - 1
					j = j + 1
				temp = temp.next
		return head


from typing import Optional
import math

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

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		ans = head
		while head != None:
			if head.data < 3:
				head.data = 2
			elif checkPrime(head.data) != 1:
				x = head.data
				i = 1
				while True:
					if checkPrime(x - i):
						head.data = x - i
						break
					if checkPrime(x + i):
						head.data = x + i
						break
					i += 1
			head = head.next
		return ans


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		from bisect import bisect
		mvalue = 2 * 10 ** 4
		primes = [True] * mvalue
		primes[0] = primes[1] = False
		for i in range(2, mvalue):
			if primes[i]:
				for j in range(i * i, mvalue, i):
					primes[j] = False
		primes = [i for (i, v) in enumerate(primes) if v]
		t = head
		while t:
			i = bisect(primes, t.data)
			d1 = abs(primes[i - 1] - t.data)
			d2 = abs(primes[i] - t.data)
			t.data = primes[i - 1] if d1 <= d2 else primes[i]
			t = t.next
		return head


from typing import Optional

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		mat = [True] * 100001
		i = 2
		mat[1] = False
		mat[0] = False
		while i * i <= len(mat):
			if mat[i]:
				for j in range(i * i, len(mat) + 1, i):
					try:
						mat[j] = False
					except:
						continue
			i += 1
		temp = head
		while temp:
			val = temp.data
			if mat[val]:
				temp = temp.next
			else:
				i = val
				while mat[i] != True:
					i -= 1
				diff = abs(val - i)
				j = val
				while mat[j] != True:
					j += 1
				diff1 = abs(val - j)
				if diff1 >= diff:
					temp.data = i
				else:
					temp.data = j
				temp = temp.next
		return head


from typing import Optional
from math import sqrt

class Solution:

	def primeList(self, head: Optional['Node']) -> Optional['Node']:

		def isprime(n):
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		temp = head
		while temp:
			a = temp.data
			if a == 1:
				temp.data = 2
			elif isprime(a):
				pass
			else:
				(l, r) = (a, a)
				(c1, c2) = (0, 0)
				while c1 == 0 and c2 == 0:
					l -= 1
					r += 1
					if l > 1 and isprime(l):
						c1 = 1
					if isprime(r):
						c2 = 1
				if c1 and c2:
					if r - a < a - l:
						temp.data = r
					else:
						temp.data = l
				elif c1:
					temp.data = l
				elif c2:
					temp.data = r
			temp = temp.next
		return head


from typing import Optional

class Solution:

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

	def nearest(self, n):
		if self.isPrime(n):
			return n
		for i in range(1, n + 1):
			if self.isPrime(n - i):
				return n - i
			if self.isPrime(n + i):
				return n + i

	def primeList(self, head: Optional['Node']) -> Optional['Node']:
		curr = head
		while curr:
			curr.data = self.nearest(curr.data)
			curr = curr.next
		return head