How to write a python program that finds the first n numbers that are not divisible by any other pri-CodePudding

I need to create a program that takes user input n and the finds the first n numbers that aren't divisible by any other prime numbers except 2, 3, and 5. This is what I've got so far:

def is_divisible(i):
    for k in range(7, i):
        if is_prime(k) == 1 and i % k == 0:
            return 1
        else:
            return 0


def is_prime(k):
    for j in range(2, k):
        if k % j == 0:
            return 0
        else:
            return 1


while True:
    while True:
        while True:
            try:
                n = input("How many numbers do you want to find: ")
                n = n.replace(" ", "")
                n = int(n)
                break
            except:
                print("Input only natural numbers")
                continue

        if n == 0:
            print("Input only natural numbers")
            continue
        else:
            break

    count = 0
    i = 0
    while count < n:
        if i % 2 == 0 and i % 3 == 0 and i % 5 == 0 and is_divisible(i) == 0:
            print(i)
            count  = 1
            i  = 1
        else:
            i  = 1

    repeat = input("To repeat press (1), to end press anything else: ")
    if str(repeat) == "1":
        continue
    else:
        print("Bye!")
        break

If asked to find 10 numbers the program outputs:

The program didn't print 210 (which is divisible by 7) so the algorithm seems, at least, partly correct, but 330 is printed (which is divisible by 11) and I can't figure out why. If I manually change i to 330 and k to 11, the is_prime function correctly finds that 11 is a prime number, but the is_divisible function still returns 0. I can't figure out what's wrong. Any help will be greatly appreciated!

Thanks!

CodePudding user response：

First, you need to fix your is_prime like @Barmar mentions above

Note, this can be optimized in multiple ways, the simplest of which is to only check for j in range(2, int(math.sqrt(k)) 1) because a number k won't have any prime factors greater than sqrt(k). Also, we can memorize all the prime numbers found so far, so that if the same number is checked multiple times, subsequent checks are much faster. You can use better algorithms to check if a number is prime, but this should suffice for our purposes.

import math

# A set to remember prime numbers
primes = set()

def is_prime(k):

    if k == 1: return False       # 1 is not prime
    if k in primes: return True   # Check remembered prime numbers    

    # Check all numbers in the closed interval [2, sqrt(k)]
    for j in range(2, int(math.sqrt(k)) 1):
        if k % j == 0:
            return False
    
    # Prime number, so remember it
    primes.add(k)
    return True

The first n numbers that aren't divisible by any prime numbers other than 2, 3, and 5

Since your number needs to be divisible by 2, 3, and 5, you don't need to look at all numbers as you do currently. Just look at multiples of 2 * 3 * 5, i.e. multiples of 30, since those are the only numbers that are going to be multiples of 2, 3, and 5.

So now your problem becomes: "Print 30 * i, where i is not a multiple of a prime number other than 2, 3, and 5. i.e., you need to get the prime factors of i, and check that this set contains only 2, 3, and 5.

There are a number of ways to get the prime factors of a number. Here's a simple one:

def prime_factors(k):
    # If k is prime, it is its only prime factor
    if is_prime(k): 
        return {k}

    factors = set()

    # If divisible by 2, add 2 as a prime factor
    if k % 2 == 0: 
        factors.add(2)    

    # Check all odd numbers in the closed interval [3, k//2]
    for i in range(3, k//2 1, 2):
        if k % i == 0 and is_prime(i):
            factors.add(i)

    return factors

Now that we've defined our helper functions, we just need to call them:

n = 10

i = 1
count = 0
while count < n:
    factors = prime_factors(i)
    # If we remove {2, 3, 5} from factors, do we get an empty set?
    if not factors.difference({2, 3, 5}):
        print(2 * 3 * 5 * i)
        count  = 1
    i  = 1

Which prints:

If you are indeed looking for regular numbers as @Mark and @Kelly suggest in their comments, then you simply skip the multiplication by 2 * 3 * 5:

n = 10

i = 1
count = 0
while count < n:
    factors = prime_factors(i)
    # If we remove {2, 3, 5} from factors, do we get an empty set?
    if not factors.difference({2, 3, 5}):
        print(i)
        count  = 1
    i  = 1

gives:

CodePudding user response：

Here's a bit of code that looks for values that have other factors besides 2,3,5. If there are other factors in there, they must be other prime values because we remove the prime factors 2,3,5 from the number.

primes = [ 2, 3, 5] 

count = 10

answers = []
value = 2
while len(answers) < count:
  
  test_value = value
  for prime in primes:
    while test_value % prime == 0:
      test_value //= prime

  if test_value == 1:
    answers.append(value)

  value  = 1

print(answers)

CodePudding user response：

Your is_divisible method basically only checks 7 and then returns either 1 or 0. You want to check all the numbers in the range.

def is_divisible(i):
    for k in range(7, i):
        if is_prime(k) == 1 and i % k == 0:
            return 1
    return 0

Your is_prime method suffers from this issue as well:

def is_prime(k):
    for j in range(2, k):
        if k % j == 0:
            return 0
    return 1

Fixing these issues, however, is going make this algorithm EXTREMELY slow so you will need to consider some strategies that will make it faster. Caching the numbers that you have already checked for primeness would be a start.