CODEWITHSUNDEEP
pythonbooleanprimes
Arturo Castillin
Arturo Castillin

Reputation: 61

Strange output when trying to find prime numbers Python

Ok, so I admittedly am kind of a noob, and I've been going through a course on udemy for programming. The problem is asking to write a function that finds all the prime numbers up to the number given. So I started writing the following code to extract the numbers that are not even, as well as the numbers not evenly divisible by 3 just to start:

def count_primes(num):
    num_list5 = []
    for i in range(num + 1):
        print(i)
        if i % 2 != 0 or i % 3 != 0:
            num_list5.append(i)
    
    return num_list5

When I call the function with a number of 100 like: count_primes(100) In the output, I get the num_list5 showing all the numbers in the range except for 6 and multiples of 6:

[1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14 ...]

Its like the if statement is doing an AND operation here... because 6 would be divisible by 2 AND 3. Is this a bug or something? Or am I not understanding and/or operations correctly?

What's weird is that it was working at one point and after making a change and reverting it, it started doing this...

I'm using VSCode and Jupyter notebooks and tried both Python 3.8.5 64-bit and 3.9.4 64-bit on Ubuntu 20.04

Upvotes: 5

Views: 900

Answers (4)

Arturo Castillin
Arturo Castillin

Reputation: 61

After figuring out the propositional math and de Morgan's Law as someone pointed out, I was able to come up with a pretty simple solution using or and mod operators and only goes through a the sequence once:

def count_primes(num):

    num_list5 = []

    for i in range(2, num + 1):
        if i == 2 or i == 3 or i == 5 or i == 7:
            num_list5.append(i)
        if not (i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0):
            num_list5.append(i)
    
    return num_list5

print(count_primes(100))

Upvotes: 0

rossum
rossum

Reputation: 15693

We know some facts about prime numbers which you can use in your program. Negative numbers, 0 and 1 are not prime. 2 is the only even prime. A prime number only has itself and 1 as factors. From multiplication we know that if a x b = c then one of a, b is <= sqrt(c). That last fact helps us cut down the number of trial divisors we have to test. We can test for a prime by looking for a number that divides the target but is not the target itself or 1. If we find such a number then the target is not prime.

Here is some pseudocode to help:

function isPrime(num)
  // 1, 0, negatives not prime.
  if (num < 2)
    return false
  end if
  
  // 2 is the only even prime.
  if (num MOD 2 = 0)
    return (num = 2)
  end if

  // Try odd factors up to square root.
  limit <- 1 + sqrt(num)
  for (test <- 3; test < limit; test <- test + 2)
    if (num MOD test = 0)
      // Not prime, we have found a factor. 
      return false
    end if
  end for

  // If we get this far then num is prime.
  return true

end function

Upvotes: 0

LPR
LPR

Reputation: 390

If you are looking to generate all primes less than num, you should loop over all numbers j less than i and check if i%j is zero rather than just 2 and 3.

def count_primes(num):
    num_list5 = []
    for i in range(2, num + 1): # start at 2 because 1 and zero are not primes
        print(i)
        for j in range(2, i):
            if i%j == 0:
                break
        else:
            num_list5.append(i)
    
    return num_list5

if __name__ == "__main__":
    n = 100
    print(count_primes(n))

Note that using Sieve of Eratosthenes method, this can be done more efficiently:

import math

def count_primes_sieve(num):
    num_list5 = [False, False] + [True]*(num - 1)
    for i in range(2, math.ceil(math.sqrt(num)) + 1):
        if num_list5[i]:
            j = i * i
            while j < len(num_list5):
                num_list5[j] = False
                j += i
    return [i for i, p in enumerate(num_list5) if p]

if __name__ == "__main__":
    n = 100
    print(count_primes_sieve(n))

Upvotes: 0

Furkan
Furkan

Reputation: 361

i % 2 != 0 or i % 3 != 0 is equal to not (i % 2 == 0 and i % 3 == 0) (De Morgan's laws)

It should be i % 2 != 0 and i % 3 != 0

Upvotes: 8

Related Questions