We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
def is_probable_prime(n, k = 7):
if n < 6:
return [False, False, True, True, False, True][n]
if n & 1 == 0:
return False
s, d = 0, n - 1
while d & 1 == 0:
s, d = s + 1, d >> 1
# Use random.randint(2, n-2) for very large numbers
for a in random.sample(range(2, n - 2), min(n - 4, k)):
x = pow(a, d, n)
if x != 1 and x + 1 != n:
for r in range(1, s):
x = pow(x, 2, n)
if x == 1:
return False
elif x == n - 1:
a = 0
break
if a:
return False
return True
def f(n, k):
if n < 2 * k:
return False
if k == 1:
return is_probable_prime(n)
if k == 2:
if n % 2 == 0:
return True
else:
return is_probable_prime(n - 2)
return True
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
print("Yes" if f(n, k) else "No")
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prime Sum
You are viewing a single comment's thread. Return to all comments →
import random import sys
def is_probable_prime(n, k = 7): if n < 6: return [False, False, True, True, False, True][n] if n & 1 == 0: return False s, d = 0, n - 1 while d & 1 == 0: s, d = s + 1, d >> 1 # Use random.randint(2, n-2) for very large numbers for a in random.sample(range(2, n - 2), min(n - 4, k)): x = pow(a, d, n) if x != 1 and x + 1 != n: for r in range(1, s): x = pow(x, 2, n) if x == 1: return False elif x == n - 1: a = 0 break if a: return False return True
def f(n, k): if n < 2 * k: return False if k == 1: return is_probable_prime(n) if k == 2: if n % 2 == 0: return True else: return is_probable_prime(n - 2) return True
t = int(input()) for _ in range(t): n, k = map(int, input().split()) print("Yes" if f(n, k) else "No")