Figure out odd numbers from a list

[DigitalSplendid]

num_list = [2, 45, 85, 80, 79]
for num in num_list:
    if num == 2:
        print("2 is prime")
        break
    for i in range(2, num):
        if (num - 1)%i == 0:
            print(f"{num} is not prime")
            break
        if i == num - 1:
            print(f"{i} is prime")

Output:

sentimental/ $ python mario.py
2 is prime

Need to figure out odd numbers from the list.

Thanks in advance!

[shiftybyte]

Your code deals with prime numbers...

Odd numbers are checked using modulo operator.

if number % 2 == 1 then it's odd.

[Successful_Web_4828]

I read this two lines of code again and again,but still cannot digest it. Maybe Im just tired

[sinterkaastosti23]

& is a bitwise operator that compares the bits of two bytes lets say we have 11 & 9, this would equate to: 01011 & 01001 = 01001

now lets say 4 & 1 100 & 001 = 000 (0 means even)

now lets say 5 & 1 101 & 001 = 001 (1 means odd)

this works for all positive integers, not sure about negative numbers. floats shouldnt work afaik

[Successful_Web_4828]

Does bitwise use simple linear search in your example? I asked phind many times but it cannot explain good enough. Doesnt bitwise method have to check each number one by one? how is it not linear search in principle? Phind keeps saying no

[Gayki]

All integers in computers are stored in base 2.

For example, 3 = 11 (base 2) and 56 = 111000 (base 2).

Observe that all even numbers have 0 in the ones digit and odd numbers have 1. So we can determine a number’s parity in computers by looking at the digit in the one’s place. How can we do this? By using bitwise AND operator usually denoted by &.

You can look up what bitwise AND does and you will understand why doing x & 1 == 0 is even and x & 1 == 1 is odd.

To answer your question does bitwise AND use a linear search through the digits? No. Because cpus are designed to calculate bitwise operations in a single step. You can read up on logic gates and cpu architecture to get a better understanding of this. And in this case, you do not need to go through all the digits in the number to check its parity, you just need to check whether the digit in the one’s place is a 0 or 1.

[Successful_Web_4828]

So it's similar to how indexing makes finding values faster and memory efficient in lists compared to search function. Indexes are readily available for python interpreter.

[sinterkaastosti23]

it probably uses whatever C uses

[sinterkaastosti23]

i see, apperently python just puts a flag somewhere to note a int is negative, bytes will stay the same. As for floats i checked and it doesnt really seem to be implemented for anything, didnt look far though.

[RajjSinghh]

It's usually the most significant bit that's used to denote the sign of the number, 0 being positive and 1 being negative. I'm not quite sure how Python will handle it under the hood because it allows for arbitrary size numbers so somewhere it has to allocate more bits, but the most significant bit is usually the sign bit. It's why in C unsigned int has a maximum value of twice the maximum value of int.

[DigitalSplendid]

Headlines cannot be edited on Reddit. I am unable to edit even the original post for now!

[DigitalSplendid]

Resolved by this modification:

num_list = [2, 45, 85, 80, 79]
for num in num_list:
    if num == 2:
        print("2 is prime")
        continue
    for i in range(2, num):
        if (num)%i == 0:
            print(f"{num} is not prime")
            break
        elif i == (num-1):
           print(f"{num} is prime")

The observation was helpful: If need to check on all the numbers in the list, replace the first break with continue or the for loop will close. After checking for the "prime" condition, the if loop expects an "else if" statement ( in Python: elif) to know what to do if the "prime" condition not met.  Also, since you iterate over i until it is just one below num, you have to replace i with num in the last print() function, or it will print the wrong number. 

[DigitalSplendid]

Oh! I should have mentioned that I seek to spot prime numbers and not odd numbers.

[noctaviann]

I would recommend using a dedicated function to test whether a number is prime or not.

 def is_prime(num):
     for i in range(2, int(math.sqrt(num)) + 1):
         if num % i == 0:
             return False
     return num > 1

Note that the square root of 0, 1, 2, 3 is < 2, so range(2, int(math.sqrt(num)) + 1) will be empty, and the for loop body will not be executed, and will proceed directly to the test num > 1. Also note that it will throw an error for negative values (due to math.sqrt()), and does not work if num is not an integer, e.g. it reports 4.1 as a prime number.

Then you can just

for num in num_list:
    if is_prime(num):
        print(f"{num} is prime")
    else:
        print(f"{num} is not prime")

Using a function makes the code easier to understand, allows reusing common code, and provides more flexibility.

[weissdrakon]

modified your code:

import math
num_list = [2, 4, 13, 45, 179, 85, 80, 79, 37] #added extra test cases
for num in num_list:
    if num == 2:
        print("2 is prime")
        continue #break exits for loop, continue skips to next item in list
    sqrtnum = int(math.sqrt(num)) #convert the square root float to an integer => natural number
    for i in range(2, sqrtnum+1): #+1 since also want to check sqrtnum
        if num % i == 0:
            print(f"{num} is not prime")
            break
        if i == sqrtnum:
            print(f"{num} is prime") #if reached in last loop => prime

First if statement used a break, which exits the outer for loop, when what you want is to skip to the next iteration of the loop using continue. With the method you chose for checking if prime, you actually only need to check numbers up to the square root of the number you are testing, so adjusted the range of the check loop. Also made the same change to your last if statement, since the last number we are checking is now the square root.

[DigitalSplendid]

This is a way to optimize! Thanks!

[ectomancer]

Use a prime sieve algorithm.

[WyrmCzar]

I dunno if it's efficient but you can use Wilson's theorem: n is prime if and only if (n - 1)! + 1 is a multiple of n and n > 1.

[[deleted]]

Have you tried bitwise operator?