 # BROTHERLY LOVE

can some one suggest me a good algo on how to find the next smaller prime no. for a given no.(n).

for ex.
7 for 10.
13 is for 17…
23 for 27…and so on…

n tends to 10^9…

A solution that comes in my mind is:

1. Use an Optimized Sieve and store all prime nos upto a range(say 10^8).

2. Then for any given number n<10^8, if it is even start from n-1 otherwise from n-2 and keep decrementing n by 2, and check in the Sieve array whether its prime.

3. Otherwise check it is prime or not using remainder with all prime numbers below sqrt(n).

It should work i think… 1 Like

Use Rabin-Miller test to check that the number is prime.
For N<10^9 it is enough to check witnesses 2, 7 and 61 according to Wikipedia.
Since the largest prime gap is relatively small naive check should work fast enough.
But it depends on constraints.

1 Like

I tried 2 methods one using Sundaram’s sieve and other one using Miller’s Rabin test but both of them gave TLE . Can u tell how to optimize both the methods ?
P.S : I code in Python

Code 1 :

``````import sys,random
def miller_rabin_pass(a, s, d, n):
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in xrange(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def miller_rabin(n):
d = n - 1
s = 0
while d % 2 == 0:
d >>= 1
s += 1
for repeat in xrange(20):
a = 0
while a == 0:
a = random.randrange(n)
if not miller_rabin_pass(a, s, d, n):
return False
return True
flag=0
while 1:
if flag==1:
break
a=map(int,raw_input("").strip().split())
if len(a)!=1:
continue
flag=1
m=a
while m:
k=map(int,raw_input("").strip().split())
if len(k)!=1:
continue
b=k-1
m-=1
i=0
while not miller_rabin(b):
b-=1
print b
``````

Code 2 :

``````def sundaram3(max_n):
numbers = range(3, max_n+1, 2)
half = (max_n)//2
initial = 4

for step in xrange(3, max_n+1, 2):
for i in xrange(initial, half, step):
numbers[i-1] = 0
initial += 2*(step+1)

if initial > half:
return  + filter(None, numbers)
l=sundaram3(4294967296);flag=0
while 1:
if flag==1:
break
a=map(int,raw_input("").strip().split())
if len(a)!=1:
continue
flag=1
m=a
while m:
k=map(int,raw_input("").strip().split())
if len(k)!=1:
continue
b=k
m-=1
i=0
while 1:
if l[i]>=b:
print l[i-1]
break
i+=1
``````

P.S. : This is my first post. So I am having trouble with indenting the code on codechef platform . Sorry for that. In 2nd and 1st code while 1 : (if flag==1 one )is for full loop and in code 1: functions have indent associated with them .

Ideone for codes are http://ideone.com/KQPP9A and http://ideone.com/lERrrk . And I don’t know why it shows runtime error on Ideone but the same solutions get accepted in online judges .