3
\$\begingroup\$

I have just made what seems to me to be the first reliable prime-checking program that works. However, I am not sure if it is completely reliable, or if there are problems. It relies on list-making more than math, and it can be slow for bigger numbers. Do you think there are any problems?

def primeChecker(x):
    if x <= 1 or isinstance(x,float) == True:
        return str(x) + " is not prime"
    else:
        div = ["tepi"] #tepi denotes test element please ignore
        for i in range(1,x+1,1):
            if x % i == 0:
                div.append("d") #d denotes divisible
            else:
                div.append("n") #n denotes not divisible
        if div[1] == "d" and div[x] == "d" and div.count("n") == x - 2:
            return str(x) + " is prime"
        else:
            return str(x) + " is not prime"

def primeCheckList(d,e):
    for i in range(d,e + 1):
        print primeChecker(i)

Here are some of the tools I used in primeChecker() to see if it was working right.

print div #these are testing tools
print range(1,x+1,1)
print div[1]
print div[x]
print div[2:x]
print div.count("n")
print x - 2

edit: Barry's feedback

OK, based on what Barry told me, i was able to clean up and otherwise format my code to be more concise, no more lists needed. it seems to run smoother, and is otherwise easier to read. here it is:

def isPrime(x):
    if x <= 1 or isinstance(x,float):
        return False
    else:
        for divisor in range(2,x,1):
            if x % divisor == 0:
                return False
        return True

def primeChecker(n):
    if isPrime(n):
        return "%d is prime" % n
    else:
        return "%d is not prime" % n

def primeCheckList(d,e):
    for i in range(d,e + 1):
        print primeChecker(i)

any more feedback to give?

\$\endgroup\$
1
\$\begingroup\$

There is lots of room for improvement here. Let me give some broad guidelines:

First, Your function checking if its input is prime should return a boolean and probably be called something like isPrime or is_prime. The string you are returning is nice for being human readible, but the goal should be to build components that can be used elsewhere, and the function as written isn't really something you can build on. And given the boolean function, you can easily build your version on top of that:

def prime_checker(n):
    if is_prime(n):
        return "%d is prime" % n
    else:
        return "%d is not prime" % n

Second, there is some improper use of Booleans (and lack thereof). You have isinstance(x,float) == True. The isinstance function already returns a boolean, there's no need to compare against True. That clause can just be if x <= 1 or isinstance(x, float):. But then, does it make sense that 2.7 is not prime? Maybe that should raise an Exception. You are also building up a list of size x consisting of values that are intended to indicate whether or not the value at that index divides x. You chose:

div.append("d") #d denotes divisible

Which you realized was cryptic because you had to comment what that meant. Rather than relying on a comment to explain what you're doing, it's much better for the code to comment itself. In this case, what should we append to indicate that a number is a true divisor? How about:

div.append(True)

Third, you're building up a long list of things that should be Booleans but are instead strings. But that is a whole lot of extra work for what we actually want to count: the number of factors. The simplest explanation for why it's extra work is that first you're walking through all potential divisors, and then you're walking through it again to count how many were actual divisors. Instead, you can do this in one go:

divisors = 0
for divisor in range(1, x+1): 
    if x % divisor == 0:
        ++divisors
return divisors == 2 #because a number prime iff it has exactly 2 divisors, 1 and itself

Once you write it that way, this has lots of room for simple optimizations. For instance, obviously every integer is divisible by 1 and itself, so you can exclude those two:

for divisor in range(2, x):
    if x % divisor == 0:
        return False # because we have a divisor other than 1 or x
return True

After that, things get more interesting. For instance, let's say we're checking a number like 5077 for primality. If it is NOT prime, then there are two numbers, a and b, such that 1 < a <= b < n and a*b == n. What is the largest possible value for a as a function for n? I'll leave that as an exercise, but the last algorithm I proposed assumes the maximum possible value is x - 1, and we can do much better.

\$\endgroup\$
  • \$\begingroup\$ i must say, you kind of lost me with your last paragraph, can you explain what you are talking about? like im 5? \$\endgroup\$ – Arron Grier Oct 27 '13 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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