найти простые числа в python

Question

Мне нужно написать код, который найдет все простые числа в диапазоне чисел, а затем перечислить их, чтобы указать, какие из них простые, а какие нет, а также, если они не являются первыми, показать какие числа они делятся. Это должно выглядеть примерно так:

>>> Prime(1,10) 
1 is not a prime number 
2 is a prime number 
3 is a prime number 
4 is divisible by 2 
5 is a prime number 
6 is divisible by 2, 3 
7 is a prime number 
8 is divisible by 2, 4 
9 is divisible by 3 

до сих пор у меня есть это, которое будет только определить, какие числа являются простыми и напечатать их в списке. Я не знаю, как делать не простые числа и печатать, какие числа они делятся на. Также я получаю, что 1 - простое число.

def primeNum(num1, num2): 
    for num in range(num1,num2): 
    prime = True 
    for i in range(2,num): 
     if (num%i==0): 
      prime = False 
    if prime: 
     print (num,'is a prime number') 

Answer 1

можно хранить делители для каждого номера в списке, а затем распечатать его с ", ".join(yourList)

т.е.

def primeNum(num1, num2): 
    for num in range(num1,num2): 
     divisors = [] 
     for i in range(2,num): 
      if (num%i == 0): 
       divisors.append(str(i)) 
     if divisors: 
      print ('%d is divisible by ' %num + ', '.join(divisors)) 
     else: 
      print ('%d is a prime number' %num) 

Edit: немой ошибка синтаксиса

Answer 2

Просто добавьте печать и разрыв в позиции, в которой вы устанавливаете значение с точностью до false.

Более элегантным решением было бы сделать отдельную функцию isPrime или использовать break и else во внутреннем цикле. В любом случае это станет ненужным.

Вы можете разделить только по одному и на себя, так что это простое число по этому определению.

Answer 3

Использование решето будет делать трюк:

Пример:

from __future__ import print_function 


def primes(): 
    """Prime Number Generator 

    Generator an infinite sequence of primes 

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python 
    """ 

    # Maps composites to primes witnessing their compositeness. 
    # This is memory efficient, as the sieve is not "run forward" 
    # indefinitely, but only as long as required by the current 
    # number being tested. 
    # 
    D = {} 

    # The running integer that's checked for primeness 
    q = 2 

    while True: 
     if q not in D: 
      # q is a new prime. 
      # Yield it and mark its first multiple that isn't 
      # already marked in previous iterations 
      # 
      yield q   
      D[q * q] = [q] 
     else: 
      # q is composite. D[q] is the list of primes that 
      # divide it. Since we've reached q, we no longer 
      # need it in the map, but we'll mark the next 
      # multiples of its witnesses to prepare for larger 
      # numbers 
      # 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q] 

     q += 1 


def factors(n): 
    yield 1 
    i = 2 
    limit = n**0.5 
    while i <= limit: 
     if n % i == 0: 
      yield i 
      n = n/i 
      limit = n**0.5 
     else: 
      i += 1 
    if n > 1: 
     yield n 


def primerange(start, stop): 
    pg = primes() 
    p = next(pg) 

    for i in xrange(start, stop): 
     while p < i: 
      p = next(pg) 

     if p == i: 
      print("{0} is prime".format(i)) 
     else: 
      print("{0} is not prime and has factors: {1}".format(i, ", ".join(map(str, set(factors(i)))))) 

Выход:

>>> primerange(1, 10) 
1 is not prime and has factors: 1 
2 is prime 
3 is prime 
4 is not prime and has factors: 1, 2 
5 is prime 
6 is not prime and has factors: 1, 2, 3 
7 is prime 
8 is not prime and has factors: 1, 2 
9 is not prime and has factors: 1, 3