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

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

CodePudding user response：

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

CodePudding user response：

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=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

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... well I started it over an hour ago and it's still running.