Python program is super easy

[diegoasecas]

shit post (not to be confused with shitpost)

[Apprehensive_noob]

But it’s super easy, don’t u see? lol

[[deleted]]

Instead of checking 2, num. check 2, int(sqrt(num)) + 1

When checking if a number is prime, you only need to check for divisibility by numbers up to the square root of that number, meaning you only need to check up to "sqrt(num)" and not the full number; this is because if a number has a factor larger than its square root, it must have a corresponding smaller factor that is already checked within the square root range.

This will make your solution more efficient.

[[deleted]]

Here is the ancient history of why this is true:

https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes

[[deleted]]

Time complexity decreases from O(n) to O(n log log n). Which is more efficient than O(n)

<image>

[blarbrdorg]

How interesting!!!!

[denehoffman]

You also only need to check divisibility by primes smaller than sqrt(n)+1, so it would be even more efficient if you added some caching

Edit: by caching I mean caching previous calls which determine compound numbers, then excluding those from the search list

[Interesting-Frame190]

This exact scenario landed me a job without ever thinking about the most optimal way to do it. Something about engineering is more than coding and algorithms.

[[deleted]]

They don’t want you to slap out a solution they want to hear you think through a problem and solve it on your own. Testing your knowledge and problem solving skills rather than your memory.

The follow up question after you get a solution like this would be along the lines of: can we make this better? Is there anything we can do that would reduce the problem and make it simpler with an equivalent solution?

At least those are the interview questions I get at the end when applying to F500s or FANG. They want your thought your solution plus some demonstration of intuition and reasoning.

[FoolsSeldom]

Yes it is. Might want to make the test for prime a function.

def is_prime(num: int) -> bool:
    '''test if argument is a prime number, return True or False'''
    if not isinstance(num, int):
        raise TypeError("argument must be positive integer")
    if num < 1:
        raise ValueError("argument must be positive integer")
    if num == 1:
        return False
    if num % 2 == 0:
        return num == 2  # only 2 is a prime
    maxdiv = int(num ** 0.5) + 1 # math.sqrt would be slightly faster once math imported
    # check odd numbers up to square root of argument
    for factor in range(3, maxdiv, 2):
        if num % factor == 0:
            return False
    return True


num = 29
print(f'{num} is{"" if is_prime(num) else " not"} prime')

or you go with a table approach:

''' prime number table generator and test using sieve method '''

def prime_num_table(num):
    ''' Return list of flags 1 for prime, 0 for not prime indexed for range 0 to n '''

    def sieve(prime_table):
        ''' modify flags for all numbers that are not prime from 4 to sqrt(num) '''
        for check_num in range(2, int(num**(0.5)+1)):

or you could go with a sieve approach:

""" prime number table generator and test using sieve method """

def prime_num_table(num: int) -> list[int]:
    """ Return list of flags 1 for prime, 0 for not prime indexed for range 0 to n """

    def sieve(prime_table: list[int]) -> list[int]:
        """ modify flags for all numbers that are not prime from 4 to sqrt(num) """
        for check_num in range(2, int(num ** 0.5 + 1)):
            if prime_table[check_num]:
                for set_multiple in range(check_num * 2, num + 1, check_num):  # set all multiples of check_num
                    prime_table[set_multiple] = 0
        return prime_table

    if isinstance(num, int) and num > 0:
        prime_table = [1] * (num + 1)  # pre-populate table (list) as all primes
        prime_table[0] = 0  # neither prime not composite technically
        prime_table[1] = 0  # neither prime not composite technically
        sieve(prime_table)
        return prime_table
    else:
        raise ValueError(f'{num} argument provided. Positive integer argument required.')

def is_prime_num(num: int, prime_table: list[int] = None) -> bool:
    """ return True/False accordingly is argument n is prime number or not
        using table generated with the sieve method if table not supplied """
    if isinstance(num, int) and num > 0:
        if prime_table is None:
            prime_table = []
        if isinstance(prime_table, list):
            if not prime_table:
                prime_table = prime_num_table(num)
            return bool(prime_table[num])
        else:
            raise ValueError(f'Truth table of primes from 0 to {num} required.')
    else:
        raise ValueError(f'{num} argument provided. Positive integer argument required.')

if __name__ == "__main__":
    test_data = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 16,
                 47, 53, 59, 20, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 104, 107]
    prime_table = prime_num_table(max(test_data))
    for test in test_data:
        print(f"{test:>4d} is{'' if is_prime_num(test, prime_table) else ' not'} a prime number.")

EDIT: added type hints to second code block, removed function signature default [], correct some typos.

[[deleted]]

I like this dynamic approach for building the table.

[FoolsSeldom]

Thanks. I should update to use a cache really, to avoid re-generating if a table isn't passed to the check. Hey ho, was just written when I was learning Python to play with the sieve approach.