BROTHERLY LOVE

general
1

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…

2

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…:slight_smile:

1 Like
3

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
4

@anton_lunyov :

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 KQPP9A - Online Python Interpreter & Debugging Tool - Ideone.com and lERrrk - Online Python Interpreter & Debugging Tool - Ideone.com . And I don’t know why it shows runtime error on Ideone but the same solutions get accepted in online judges .

Thanks in advance