top of page

List of all non-prime numbers between two positive integers using python function

Problem

Write a function that returns a list of all non-prime numbers between two positive integers supplied as arguments. Use this is in a program that asks the user to supply two positive integers, checks that the input is valid, then calls the function and outputs the numbers in the returned list, with 10 numbers per output line.


If the user enters negative numbers or supplies non-numeric input the program should output an appropriate error message; the two numbers should be accepted in either order.

The range should be inclusive; if the user inputs 100 and 351 (or 351 and 100) these two

numbers (which are both non-prime) should be included in the output.


Implementation


#%% Function to update a string position
def update_string(txt: str, position: int, char: str) -> str:
    '''
    Update a string at the given position

    Parameters
    ----------
    txt : str
        The string to update
    position : int
        The position to update
    char : str
        The new character

    Raises
    ------
    Exception
        Either char is not a single character, or position is out of range

    Returns
    -------
    str
        The updated string

    '''
    
    if position < len(txt):
        if len(char) == 1:
           return txt[0:position] + char + txt[(position + 1):]
        
        else:
            raise Exception("from update_string: char must be a single character")
    
    else:
        raise Exception("from update_string: position must be smaller than the length of txt")
          
#%% Function to mark multiples in a range

def mark_multiples(num: int, bitstring: str) -> (bool, str):
    '''
    Marks the multiples of a given number in a bitstring denoting
    a list of numbers. Each number n is at position (n - 1).

    Parameters
    ----------
    num : int
        The number for which to mark multiples of
    bitstring : str
        The string consisting of 0's and 1's. After the marking operation,
        all positions marked with 0 are divisible by num

    Returns
    -------
    (bool, str)
        A tuple in which the bool part part denotes success of the
        marking operation, and the str part is the marked bitstring.

    '''
    
    # get the max range
    max_range: int = len(bitstring)

    # use this condition to determine if marking is possible
    if num ** 2 <= max_range:
        # mark all multiples of num
        for pos in range(num ** 2, max_range + 1, num):
            # mark the multiple as not prime if not already marked
            if bitstring[pos - 1] == '1':
                bitstring = update_string(bitstring, pos - 1, '0')

        # return tuple containing marked bitstring and denoting success
        return (True, bitstring)

    else:
        # return tuple containing unmarked bitstring and denoting failure
        return (False, bitstring)

#%% Function to return a sieved list

def get_sieve(max_range: int) -> str:
    '''
    Generates a bitstring denoting a list of numbers. Each number n is 
    at position (n - 1). After the sieving operation, prime number
    positions are marked as 1's, and positions with prime multiples
    are marked as 0's

    Parameters
    ----------
    max_range : int
        The upper limit of the bitstring

    Returns
    -------
    str
        A bit string denoting a list of primes (marked with 1)
        and a non primes (marked with 0)

    '''
    
    if max_range > 0:
        # get an initial bitstring of 1's of length max_range
        n_bitstring: str = "1" * max_range

        # initialize the variables used in keeping track of
        # the computation:
        
        # 1 is not a prime, mark the position of 1 as false
        n_bitstring = update_string(n_bitstring, 0, '0')
        
        # keeps track of whether new multiples where marked 
        # by the mark multiples function. The variable is marked 
        # True because the first marking operation in the previous
        # line was successful
        new_multiples_marked: bool = True
        
        # r_bitstring is the result bitstring to finally return
        r_bitstring: str = n_bitstring     

        # the next prime is 2 at position 1
        prime_pos: int = 1           

        # initialize the first prime
        prime: int = 2
        
        # repeat the marking operation while the previous marking 
        # operation is succeessful
        while new_multiples_marked:
            # mark the multiples of prime in r_bitstring
            sieve_result =  mark_multiples(prime, r_bitstring)

            # get success/failure of marking operation
            new_multiples_marked = sieve_result[0]    
            
            # get the result bitstring
            r_bitstring = sieve_result[1]       
            
            # try getting the position of the next prime
            try:
                # get the position of the prime to be used for the next iteration
                # might throw an exception if index not found
                prime_pos = r_bitstring.index('1', prime_pos + 1) 
                        
                # get the next prime
                prime = prime_pos + 1

            except:
                pass

        # return the result bitstring
        return r_bitstring

    else:
        return ""


#%% Get user input

def get_input(prompt: str) -> None:
    '''
    Prompts the user for input until the user enters a non negative
    whole number

    Parameters
    ----------
    prompt : str
        The prompt to display to the user

    Returns
    -------
    None
        DESCRIPTION.

    '''
    
    # the number to return
    num: int = 0

    # repeat the operation indefinitely while the user
    # enters a wrong input
    while True:
        try:
            # try getting user input
            num = int(input(prompt))

        except:
            # The user entered non integer input
            print("You entered a non numeric input or a float")
            print("Please enter a non negative integer")

        else:
            if num < 0:
                # The user entered a negeative number
                print("You entered a negative number")
                print("Please enter a non negative integer")

            else:
                # User input OK; stop the loop
                break

    # return the input
    return num

#%% Function to printout a list of numbers

def printout(lst: list, num_per_line: int) -> None:
    '''
    Print out the list line by line, with num_per_line
    items per line

    Parameters
    ----------
    lst : list
        The list to print out
    num_per_line : int
        The number of items per line

    Raises
    ------
    Exception
        num_per_line param must be greater than 0

    Returns
    -------
    None
        DESCRIPTION.

    '''
    
    if num_per_line > 0:
        # The final output list stores the output line by line
        output_list: list = []

        # The number of lines having num_per_line items
        q = len(lst) // num_per_line
        
        # The last line will have r items
        r = len(lst) % num_per_line
        
        # the max number of digits. This will help with formatting
        # each number. If the maximum num was 512, max_num_digits
        # will be 3, so all numbers will be formatted to have
        # a width of 3.
        last_num = lst[len(lst) - 1]
        max_num_digits: int = len(str(last_num))

        # Construct the output list, line by line
        # run the loop q times
        for i in range(0, q):
            # get the start of the list slice
            start = i * num_per_line
            
            # get the end of the list slice
            end = start + num_per_line

            # construct a list of numbers formatted to the width max_num_digits
            # and selected from the range  (start:end)
            tlist = [f"{str(n):>{max_num_digits}}" for n in lst[start:end]]
            
            # convert the tlist to a string and append it to output list
            output_list.append(", ".join(tlist))

        # append the leftovers:
            
        # get the start and end for the last list slice
        start = q * num_per_line
        end = start + r

        # construct a list of numbers formatted to the width max_num_digits
            # and selected from the range  (start:end)
        tlist = [f"{str(n):>{max_num_digits}}" for n in lst[start:end]]
        
        # convert the tlist to a string and append it to output list
        output_list.append(", ".join(tlist))


        # print out the final output list
        print("\n".join(output_list))

    else:
        # since num_per_line is greater than 0, raise an exception
        raise Exception("from printout: num_per_line param must be greater than 0")
    

#%% Get non primes
def extract_non_primes(bitstring: str, lower_limit: int, 
                       upper_limit: int) -> list:
    '''
    Extract the non primes from the input bitstring

    Parameters
    ----------
    bitstring : str
        The string consisting of 0's and 1's. All positions marked
        with 1's are prime, and all positions marked with 0's are
        non primes
        
    lower_limit : int
        The lower limit of the range
    upper_limit : int
        The upper limit of the range

    Returns
    -------
    list
        A list containing the non primes in the 
        range (lower_limit:upper_limit), both inclusive

    '''
    
    # create a list of numbers from the bitstring:
        
    # all elements are in the form (i + 1), since if i
    # is the position, (i + 1) will be the number at that position    
    # Also, the lower_limit and upper_limit denote the numbers
    # not positions
    
    # Since all elements are in the form (i + 1), the lower_limit has
    # to be shifted back (that is, lower_limit - 1), otherwise it 
    # will be skipped
    
    # The upper limit of the range will be included since all elements
    # are in the form (i + 1)
    return [(i + 1) for i in range(lower_limit - 1, upper_limit) 
                    if bitstring[i] == '0']

#%% The main program

# get the range limits
fnum: int = get_input("Enter the beginning of the range: ")
snum: int = get_input("Enter the end of the range: ")

# check the order in which the numbers were entered
# and correct them
if fnum <= snum:
    lower_limit = fnum
    upper_limit = snum

else:
    lower_limit = snum
    upper_limit = fnum

# get the sieved list of numbers from 1 to max
bitstring = get_sieve(upper_limit)

# get the non primes in the range (lower_limit:upperlimit) inclusive
non_primes_in_range = extract_non_primes(bitstring, lower_limit, upper_limit)

# display the non primes
print(f"Non Primes in range: {lower_limit} to {upper_limit}")
printout(non_primes_in_range, 10)

output:


Here you can get help in any python programming homework, assignment or project. We are providing code with well commented and delivered task within your time frame. Hire expert and get instant help with an affordable price.


Send your requirement details at:


realcode4you@gmail.com

If you have any query then also comment in below comment section and get support with our expert.


Commentaires


bottom of page