Looping and finding composite/prime numbers and saving it to a set

user_14423033 0
Viewed 112

I am trying to loop through a list of values and find out whether each number is either prime or composite and save it in the set under the function. The problem I am having is that it's not finding anything and it's just saving a running count of numbers. For example, this script is just saving all numbers from 1-19. I also understand that it's not actually saving the values in one set but I'll figure that out. Mostly need help on actually getting the values to be prime/composite.

def prime(num):
    prime_set = set()
    composite_set = set()
    for i in range(2,num):
        if num % i == 0:
            composite_set.update([num])
        else:
            prime_set.update([num])
    return(prime_set)

for num in range(1,20):
    print(num,prime(num))
python
2 Answers

Because of your if/else block in prime, num will be added to prime_set if any number in range(2,num) fails to divide evenly into num. Since num-1 doesn't divide evenly into num whenever num is at least 3, num will always be added to prime_set.

What you want to do is only add num to prime_set if you failed to find any divisors. The simplest change to your code would be.

def prime(num):
    prime_set = set()
    composite_set = set()
    for i in range(2,num):
        if num%i == 0:
            composite_set.add(num)
            break # You don't need to keep searching

    if not composite_set: # That is, it's empty.
        prime_set.add(num)

    return prime_set
user_80755400

You could also consider implementing the Sieve of Erastosthenes algorithm for generating a set of primes which is going to be much faster; it works by continuously eliminating multiples of all primes as they are found:

def primes(n):
  # Set prime to true for all values >= 2 initially
  primes = [i >= 2 for i in range(n + 1)] 

  # iterate to set all multiples of the considered prime to composite
  p = 2
  while (p * p <= n): 
    if primes[p]: 
      for i in range(p * 2, n + 1, p):
        primes[i] = False
    p += 1

  # composite_set = set([i for i, p in enumerate(primes) if not p])
  prime_set = set([i for i, p in enumerate(primes) if p])
  return prime_set

On my machine this algorithm takes less than 200 ms to generate all primes up to 1 million.

user_5764370
Related