0

I am trying to modify my program to create two empty lists: prime and non_prime. and test if the random number in the list is a prime number or not a prime number. If the number is prime, I want to append it to prime number list. If not, I want to be able to add it to non_prime list. I tried to find the prime and non prime number from the random number list but I get the same output for prime and non prime number. Can anyone help me?

 import random

 def main():
      num = [random.randint(1,100) for _ in range (20)]
      print(num)

      lowest = min(num)
      print("The lowest number is: ", lowest)

      highest = max(num)
      print("The highest number is: ", highest)

     total = 0.0
     for value in num:
        total += value

     average = total / len(num)
     print("The average is: " , average)


     prime = [num]
     for a in range (1, 101):
        for b in range(2, a):
            if a % b == 0:
                break
        else:
            prime.append(a)
     print("The prime numbers are: " , prime)

    nonprime = [num]
    for x in range (1, 101):
        for y in range(2, x):
            if x % y == 0:
                break
        else:
            nonprime.append(x)
    print("The non prime numbers are: " , nonprime)
vish
  • 43
  • 2
  • 7

2 Answers2

1

You could use my handy-dandy one-liner prime-checker! 

def is_prime (x): return True if x in [2,3] else not any (x % n == 0 for n in range (2, int (x ** 0.5) + 1))

Now, you use this function in your for loop:

for num in range (1, 101): 
    if is_prime (num): prime.append (x)
    else: nonprime.append (x)

BTW, if anyone wants to help me improve that function (or just wants to understand it), just comment below! It pretty much makes a list of all the factors then returns true or false based on the length of that list (or True if the num is 2 or 3)

Levi Lesches
  • 1,508
  • 1
  • 13
  • 23
  • 2
    your prime checker is highly inefficient. It should test divisors only up to sqrt(x) (included) otherwise it's too complex/slow – Jean-François Fabre Feb 28 '18 at 02:24
  • Ok, thanks! I didn't know much about factorizing numbers so I just went to the safe side when I made this. I edited the answer now. – Levi Lesches Feb 28 '18 at 02:25
  • with your new formula, `49` is prime. sqrt(x) must be included. – Jean-François Fabre Feb 28 '18 at 02:26
  • 1
    don't import math for this. do `range(2,int(x**0.5)+1)`. Check your code. You cannot use range with float boundaries – Jean-François Fabre Feb 28 '18 at 02:28
  • That returns **many** false positives and negatives. What if I just range to x/2? – Levi Lesches Feb 28 '18 at 02:32
  • forgot to cast to int. Hey _you_ answered. Now finish the job :) – Jean-François Fabre Feb 28 '18 at 02:33
  • OK, It is good now. I changed the length checking and `ranged` to (x**0.5) + 1. Confirmed it works. Thanks! – Levi Lesches Feb 28 '18 at 02:37
  • you can improve it even more, using `any` on a generator expression instead of `len`. `len` won't stop even if one divisor is found. You don't need to compute all divisors. If you find one, the number isn't prime. – Jean-François Fabre Feb 28 '18 at 02:41
  • Alright. That should do it -- hopefully. Again, thanks for your help, I use this sometimes and it feels good knowing it's optimized. – Levi Lesches Feb 28 '18 at 02:47
  • Your "fancy one liner" performs _way_ more checks that necessary. Is there a reason you think you need a one-liner? Take a look here for actual, efficient ways to calculate primes: https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n – g.d.d.c Apr 21 '18 at 23:26
  • @g.d.d.c what extra calculations are being done? As far as I can see, it checks every number up to the square root of the number without repetitions. As for why on one line, well, why *not*? – Levi Lesches Apr 22 '18 at 00:46
  • @LeviLesches - `for n in range (2, int (x ** 0.5) + 1)` checks every divisor. That's ridiculously wasteful, all things considered. If you change the initial check from `x in [2,3]` to `0 not in [x % 2, x % 3]` and then add a step to your range (starting at _5_) you save more than _half_ of the checks. Even with that, you're _still_ wasting time because you _know_ 9 isn't a divisor, because if 9 were, three would be but you're going to check it anyway. – g.d.d.c Apr 24 '18 at 00:28
  • @g.d.d.c, my function runs near instantaneously for numbers that are way higher than anyone needs, especially the OP. It's not **bad**, it's fine for practical use. – Levi Lesches Apr 24 '18 at 18:26
  • It's also not *optimized* either. Wasted cycles are wasted cycles. What if I need to check primality for a million random numbers? Wasted checks on a non-memo-ized one-liner results in compound aggregate delays. – g.d.d.c Apr 24 '18 at 20:07
-3

Just an optimization tip. In the first loop you could calculate non prime and prime both.

def isPrime(x):
    for i in range (sqrt (x)): # from i=2 till sqrt(x)
        if x % i == 0: return False
    return True

if isPrime (x): prime.append (x)
else: non_prime.append (x)

The above is sieve algorithm

Levi Lesches
  • 1,508
  • 1
  • 13
  • 23
Amir Ali
  • 11
  • 7
  • no, no and no: prime requires all division tests to be false. non prime requires at least one division test to be false. Try to provide a working snippet instead of a pseudo code... (which doesn't work) – Jean-François Fabre Feb 28 '18 at 02:23
  • @Jean-FrançoisFabre: I *think* the pseudo-code was trying to describe the correct logic (the `for i >= 2` presumably should be `for b >= 2` to mean `a % b == 0 for all b >= 2`, though that still lacks an end case to stop testing `b` when you've reached a reasonable bound, e.g. `a` or really, `sqrt(a)`). But yeah, pseudo-code isn't all that helpful. – ShadowRanger Feb 28 '18 at 02:27
  • Thanks! I have changed it have a look. – Amir Ali Feb 28 '18 at 02:30
  • ....and I edited the code structure even further (might still be under review though). You're welcome! – Levi Lesches Mar 04 '18 at 18:41