Finding Primes Different Approach

Question

I am trying to make a program that finds primes numbers for a public-key cryptography system. I know that a prime number is a positive integer that has no positive divisors other than 1 and itself. I want to use an approach that that takes all integers from 2 to sqrt(n), to tell if it divides n or not.

I have to take a "brute force" approach that takes in an integer input seed and returns the lowest prime number; prime number >= seed.

Some examples of what I want is :

>>> prime_func(100)
101
>>> prime_func(1000)
1009
>>>prime_func(7)
7
>>>prime_func(3)
5

What I have so far is:

def prime_func(number):

    START = 2
    END = (number**0.5) + 1

    for i in range(START, END):
      if number % i == 0:
         return('Composite')
      else:
         return number

For the return ('Composite') part, I want it to instead return the closest prime number after that.

Answer 1

This can be achieved using a Sieve of Eratosthenes.

Code:

def primes_sieve(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

for value in primes_sieve(32):
    print(value)

Output:

2
3
5
7
11
13
17
19
23
29
31

See This Post.

Answer 2

Try the following code:

def prime_func(number):
    number = int(number)
    START = 2
    END = int((number**0.5)) + 1

    if number == 2:
     return 1
    if number == 1:
     return 0

    while True:
        flag = True
        for i in range(START, END):
            if number % i == 0:
                flag = False
                break
        if flag:
            return number
        else:
            number += 1

if __name__ == '__main__':
    num = int(input())
    print(prime_func(num))

Input: 100
Output: 101

Input: 1000
Output: 1009