Optimization for code that tests if a number is prime

Asked

Viewed 129 times

-2

Hello! My question is about a code that I built, where the user inserts a certain number of their choice, and the program will test whether it is prime or not, however, it is testing all the numbers between two (2) and the number inserted, which can be quite slow for large numbers (the ones indicated for the function of the code). One solution I had in mind was to build a kind of "Sieve of Eratosthenes", where the program would go eliminate all multiples of the numbers that have already been tested (as 2, 3, 5, 7 and 9), to thus accelerate the number verification process.

However, all my attempts to achieve this goal did not succeed. ** Therefore, I am questioning here if any user has any algorithm or method that I can adapt and (consequently) learn from it. Below is my code if necessary (which is probably):

import sys

def programa():
    completo = None
    while True:
        if completo == True:
            break
        print()
        print("=" * 55) 
        num = int(input("Digite um número para fazer o teste se o mesmo é primo: "))
        einteiro = isinstance(num, int)
        if num == 1:
            print()
            print("1 é primo.")
            print()
            completo = True
            break

        if num == 2:
            print()
            print("2 é primo.")
            print()
            completo = True
            break

        if einteiro == True:
            print()
            print("O número escolhido foi %d" % num)
            print()
            divisor = 2
            while divisor < num:

                teste = num % divisor
                divi = num / divisor

                if teste == 0:    
                    print("Este número não é primo! Ele conseguiu dividir pelo número %d, o resultado foi %d!" % (divisor, divi))
                    print()
                    completo = True
                    break

                if teste != 0: 
                    print()
                    print("Ele não divide por %d..." % divisor)
                    print()


            if divisor == num:
                print("Ele é primo!")
                print()
                completo = True 

        if einteiro == False:
            print("O número tem que ser inteiro!")

    while True:
        a = input("Deseja ir de novo? (y/n): ")
        if a in ('y', 'n'):
            if a == 'y':
                programa()

            else:
                print()
                print("Adeus :)")
                print("=" * 50) 
                sys.exit()

        else:
            print()
            print("Digitação Inválida!")
            print() 
            continue


programa()
python

  • Use Rosser’s theorem to find the umpteenth prime.

  • I believe that it was necessary to increase the divisor variable in your program.

  • By the definition of prime natural number: -1 is not prime; -2 is the only natural pair that is prime; - if there is no number between 2 and SQRT(n) that divides n then n is prime. With these considerations you can greatly optimize your code. Anyway it won’t be the most optimized way to determine if a number is prime.

  • int(qualquer coisa) already returns a int, don’t need to use isinstance after. To know if int() failed, you capture the ValueError - have example in the documentation. Boolean values can be tested directly: if completo: instead of if completo == True:. To print a blank line, use \n, then at first it could be print('\n{:=^55}'.format('')) - the \n skips a line, and the format =^55 fills with 55 characters = (see examples at https://docs.python.org/3/library/string.html#format-examples)

  • However, an algorithm to find prime numbers is not lacking on the Internet (including here on the site itself). Some examples: https://answall.com/q/231555/112052 | https://stackoverflow.com/q/1801391 | https://stackoverflow.com/q/2068372 | https://overfstacklow.com/q/18833759

  • This answers your question? Function that returns the smallest prime number. In PYTHON

Show 1 more comment

1 answer

0

Simplifying:

import sys

def programa():
    print("=" * 55)
    num = int(input("\nDigite um número para fazer o teste se o mesmo é primo: "))
    einteiro = isinstance(num, int)
    if num == 1:
        print("\n1 é primo.")
    elif num == 2:
        print("\n2 é primo.")
    else :
        einteiro == True ,print("\nO número escolhido foi %d" % num)


    def divisor(n):
        n=2
        teste = num % n
        divi = num / n
        if teste == 0:
            print("\nEste número não é primo! Ele conseguiu dividir pelo número %d, o resultado foi %d!" % (n, divi))
        elif teste != 0:
            print("\nEle não divide por %d..." % (n))
        elif n == num:
            print("\nEle é primo!")
        else:
            einteiro == False
            print("\nO número tem que ser inteiro!")

    a = input("Deseja ir de novo? (y/n): ")
    if a in ('y', 'n'):
        if a == 'y': programa()
        elif a=='n':
            print("\nAdeus")
            print('='*50)
        else:
            a!='n'or 'y'
            print("\nDigitação Inválida!")



programa()

Browser other questions tagged python

You are not signed in. Login or sign up in order to post.