is_prime(n) function question

[scsi]

Hello, i would like to ask you help with my code, i can't understand why exactly it doesn't work like i am expecting :). I am working through "How to Think Like a Computer Scientist" by Jeffrey Elkner, Allen B. Downey, and Chris Meyers so i am still doing my first steps.

def is_prime(n):
     i = 2
     while n > i:
        if n % i != 0:
           return True
        else:
           return False
        i += 1

it seems that

i += 1

statement not functioning at all.

Thanks for your time. Any help would be appreciated!

[Gribouillis]

It should be

def is_prime(n):
     i = 2
     while n > i:
        if n % i != 0:
           i += 1
        else:
           return False
     return True

but this code is inefficient. Search this forum for similar functions.

[scsi]

ok so now i have:

def is_prime(n):
    if n < 3:
       return False
    i = 2
    while n > i:
       if n % i != 0:
          i += 1
       else:
          return False
    return True

it seems it works fine for me, now :), maybe you could explain why it's inefficient?

[Gribouillis]

ok so now i have:

def is_prime(n):
    if n < 3:
       return False
    i = 2
    while n > i:
       if n % i != 0:
          i += 1
       else:
          return False
    return True

it seems it works fine for me, now :), maybe you could explain why it's inefficient?

First, 2 is a prime number.
It's inefficient because you are testing too many divisors. It would suffice to test all numbers up to n ** 0.5 instead of n. There are other techniques to test less numbers. Efficient primality tests are a jungle, see wikipedia to start with. Also there are very fast probabilistic primality tests, which give primality with a high but non certain probability.

[scsi]

Thank you!

[scsi]

i have one more question.. for example i have program which counts even numbers:

def num_even_digits(n) 
    numeven = 0
    while n:
        temp = n / 10
        if (n - (temp * 10)) % 2 == 0:
            numeven += 1
        n = temp
    return numeven

i would like to know what 7th line does, why it's necessary to resign n value at the end?

n = temp

[TrustyTony]

I will check, did not catch the logic first. not the way I would program it. Does not look idiomatic Python. Not at computer at the moment.

Print statements are useful to see what happens:

def num_even_digits(n):
    numeven = 0
    while n:
        temp = n / 10
        if (n - (temp * 10)) % 2 == 0:
            numeven += 1
        print n, temp, n - (temp * 10)
        n = temp
    return numeven

def digits(n):
    while n:
        n, d = divmod(n, 10)
        yield d

def num_even_tony(n):
    return sum((d & 1) == 0 for d in digits(n))

test = 398168173648013914787               
print(num_even_digits(test))

print(num_even_tony(test))

"""Output:
398168173648013914787 39816817364801391478 7
39816817364801391478 3981681736480139147 8
3981681736480139147 398168173648013914 7
398168173648013914 39816817364801391 4
39816817364801391 3981681736480139 1
3981681736480139 398168173648013 9
398168173648013 39816817364801 3
39816817364801 3981681736480 1
3981681736480 398168173648 0
398168173648 39816817364 8
39816817364 3981681736 4
3981681736 398168173 6
398168173 39816817 3
39816817 3981681 7
3981681 398168 1
398168 39816 8
39816 3981 6
3981 398 1
398 39 8
39 3 9
3 0 3
9
9
"""

EDIT: both versions of functions yours and mine report 0 has 0 even digits, would need to special case that.