3
\$\begingroup\$

That was an easy one to solve but the problem lies in the efficiency since it checks every single digit of the number while converting to integers. I'm receiving TLE (i.e. Time Limit Exceeded) on the site so I have to increase its performance.

So its hard to explain but the exercise asks for the return value to be "Super" when the number is prime and all of its digits are too, return "Primo" when the number is prime but its digits are not, return "Nada" When the whole number is not prime. The test cases end with EOF.

Its worth mentioning that only built-in modules are accepted by the site. I tried using the well known (and much faster) sympy.isprime method, but it's from a 3rd party module so it wasn't accepted, sadly.

Again, I solved it, but I need a bump in the efficiency since there are 1018 numbers in the test cases and more than 200 test cases and I need to solve it in 2 seconds:

def is_prime(n):
    if n in range(0, 2):
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


while True:
    try:
        data = input()
    except EOFError:
        break
    if is_prime(int(data)):
        for j in data:
            if not is_prime(int(j)):
                print("Primo")
                break
        else:
            print("Super")
    else:
        print("Nada")
\$\endgroup\$
4
  • \$\begingroup\$ How big can the numbers be? \$\endgroup\$ Dec 12, 2017 at 19:01
  • \$\begingroup\$ 1 to 10^18 @OscarSmith \$\endgroup\$
    – Mateus
    Dec 12, 2017 at 19:07
  • \$\begingroup\$ link please for online test? \$\endgroup\$
    – phy nju
    Dec 14, 2017 at 16:48
  • \$\begingroup\$ @phynju urionlinejudge.com.br/judge/pt/problems/view/2674 \$\endgroup\$
    – Mateus
    Dec 14, 2017 at 18:56

1 Answer 1

2
\$\begingroup\$

The easiest improvement to make is to only go up to n**.5 inisprime This yields a quadratic speedup. The next obvious improvement is to not convert each digit to an int, but rather just use if j not in "2357":. This saves time in two ways: First, it skips an int conversion, and secondly, it uses one check instead of a for loop.

\$\endgroup\$
2
  • \$\begingroup\$ That worked!, I changed for i in range(2, n): to for i in range(2, int(n ** 0.5) + 1): Thats saved 1.2 secods(!) and changedif not is_prime(int(j)): to if j not in "2357": that save 0.6 amazing, thanks a lot \$\endgroup\$
    – Mateus
    Dec 12, 2017 at 19:18
  • \$\begingroup\$ no problem. You could improve performance more using a more sophisticated is_prime (like aks for example), but if this is enough faster, then it's not worth it. \$\endgroup\$ Dec 12, 2017 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.