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…
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:
Use an Optimized Sieve and store all prime nos upto a range(say 10^8).
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.
Otherwise check it is prime or not using remainder with all prime numbers below sqrt(n).
It should work i think…
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.
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[0]
while m:
k=map(int,raw_input("").strip().split())
if len(k)!=1:
continue
b=k[0]-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 [2] + 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[0]
while m:
k=map(int,raw_input("").strip().split())
if len(k)!=1:
continue
b=k[0]
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 .
Thanks in advance