Python program to find 5 prime numbers above and below a given integer

Question

I am having trouble writing a program that finds 5 prime numbers above and below a user inputted integer "n"

Note: if there are fewer than 5 primes smaller print as many as there are. If n is a prime itself it should not be included. No lists or functions are allowed

This is the output that I should get:

Please enter n: 20
Larger prime numbers: 23 29 31 37 41
Smaller prime numbers: 19 17 13 11 7

This was my attempt:

n = int(input("Number: "))
# n = 20
count1 = 0
x = 2

while count1<5:
    for i in range(2, n+x):
        if (n+x) % i ==0:
            break
        else:
            print(n+x)
            count1 += 1
            break
    x +=1

When you say "no lists are allowed," what do you mean? The code is not able to remember what it's found is prime? — jpf, Oct 09 '21 at 00:20
Yeah exactly. I'm just supposed to print the prime number as soon as it's found — soup, Oct 09 '21 at 00:22
What happens when you step through the program in a debugger? Have you looked at what the output is and how it compares to your expectations? For instance, why it's printing every other number starting at 23? Is an if-else block where all conditions lead to a `break` what you were trying to achieve? It's normal to be stuck, but getting wrong output from 9 lines of code seems like a situation where you might share some attempt at trying to debug. A helpful guide is Eric Lippert's excellent [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — kcsquared, Oct 09 '21 at 00:34

score 2 · Answer 1 · answered Oct 09 '21 at 01:18

This code works by:

counting up after number until reaching five primes
counting down before number until reaching five primes (stopping at 2)
doesn't use any functions or lists (except modulo function which I assume is okay)

Code

n = int(input('Please enter n: '))
# Try larger numbers than n
print('Larger prime numbers:', end = ' ')
num = n + 1
cnt = 0
while True:
    for i in range(2, num-1):     # prime test
        if num % i == 0:
            break
    else:
        print(num, end = ' ')     # was prime
        cnt += 1
        if cnt == 5:
            break
    num += 1

# Try smaller numbers than n
print('\nSmaller prime numbers:', end = ' ')
cnt = 0
num = n - 1
while num > 1:
    for i in range(2, num-1):    # prime test
        if num % i == 0:
            break
    else:
        print(num, end = ' ')    # was prime
        cnt += 1
        if cnt == 5:
            break
            
    num -= 1

Test

Please enter n: 20
Larger prime numbers: 23 29 31 37 41 
Smaller prime numbers: 19 17 13 11 7

jpf · Answer 2 · 2021-10-09T12:36:21.150

The answer in this post provides an excellent functional form to test for primality (AKS primality test):

How to create the most compact mapping n → isprime(n) up to a limit N?

and the test does not require any "memory" of primes found.

The task is then to encode that function without making it an actual function.

n = int(input("Number: "))
M=5

print(f'{M} primes below {n}: ',end='')
itest=n-n%2-1 # number is odd, and is below input number
nab=0
while nab<M:
  if itest == 2:
    print(itest,end=' ')
    nab+=1
    break
  if itest == 3:
    print(itest,end=' ')
    nab+=1
    itest-=1
    continue
  if itest % 2 == 0:
    itest-=2
    continue
  if itest % 3 == 0:
    itest-=2
    continue

  i = 5
  w = 2

  ipass=True
  while i * i <= itest:
    if itest % i == 0:
      ipass=False
      break
    i += w
    w = 6 - w
  if ipass:
    print(itest,end=' ')
    nab+=1
  itest-=2

print('')

print(f'{M} primes above {n}: ',end='')
itest=n+n%2+1 # number is odd, and is above input number
nab=0
while nab<M:
  if itest == 2:
    print(itest,end=' ')
    nab+=1
    itest+=2
    continue
  if itest == 3:
    print(itest,end=' ')
    nab+=1
    itest+=2
    continue
  if itest % 2 == 0:
    itest+=2
    continue
  if itest % 3 == 0:
    itest+=2
    continue

  i = 5
  w = 2

  ipass=True
  while i * i <= itest:
    if itest % i == 0:
      ipass=False
      break
    i += w
    w = 6 - w
  if ipass:
    print(itest,end=' ')
    nab+=1
  itest+=2

The output for 22, for example is

Number: 22
5 primes below 22: 19 17 13 11 7
5 primes above 22: 23 29 31 37 41

and another example:

Number: 131553423669295
5 primes below 131553423669295: 131553423669257 131553423669181 131553423669097 131553423669043 131553423668977
5 primes above 131553423669295: 131553423669299 131553423669347 131553423669413 131553423669419 131553423669439

Time Test

This algorithm is much faster for larger numbers.

For example, a timeit test on this algorithm for the number 5564445, with 1000 executions, took 2.66 seconds. With the naive approach of dividing by every number until a divisor is found, takes 1hr 40 minutes.

Python program to find 5 prime numbers above and below a given integer

2 Answers2