Печать простых чисел в диапазоне - PullRequest
Новая
       24

Печать простых чисел в диапазоне

1 голос
/ 08 марта 2020 
k=int(input())
res=[2]
for i in range(2,k+1):
    if i%2==0:
       continue 
    else:
      for j in range(2,i):
          if i%j==0 or j%2==0 :
              break
      else:
             res.append(i)
print(res)

Этот код предназначен для поиска простых чисел в заданном диапазоне чисел. Я попытался запустить код, но в списке только номер 2. Может кто-нибудь сказать мне, что происходит? Если я удаляю j%2==0, это работает. Я просто хочу знать свою ошибку.

Ответы [ 3 ]

1 голос
/ 08 марта 2020

Вы должны использовать свой текущий результат, чтобы ускорить ваш процесс. Вам нужно только проверить делимость на простые числа. Но вы строите список простых чисел. Так что используйте его! 

k=int(input())
primes=[]
for i in range(2,k+1):
    if all(i%p!=0 for p in primes):
        primes.append(i)

Вы также можете улучшить, выбрав только простые элементы, которые уступают sqrt (i), как предлагали другие. 

import math
k=int(input())
primes=[]
for i in range(2,k+1):
    j=math.sqrt(i)
    if all(i%p!=0 for p in primes if p<=j):
        primes.append(i)
0 голосов
/ 08 марта 2020

Ваш код имел одну проблему, во внутреннем l oop условие or неверно, как выделено @ kederra c. Вам не нужен j% 2 == 0, так как j всегда начинается с 2, а i%j==0 уже охватывает условие 

k=int(input())
res=[2]
for i in range(2,k+1):
    if i%2==0:
       continue 
    else:
      for j in range(2,i):
          if i%j==0 :
              break
      else:
             res.append(i)
print(res)
0 голосов
/ 08 марта 2020

во внутренней переменной l oopj начинается со значения 2, и затем у вас есть оператор if, который всегда True, потому что j%2==0 всегда 2%2==0, что всегда True, поэтому вы всегда break с первого шага внутренней for l oop итерации

вы можете использовать: 

import math 

k=int(input())
res=[]
for i in range(2, k+1):
    for x in range(2, int(math.sqrt(i) + 1)):
        if i % x == 0 :
            break
    else:
        res.append(i)
# k = 20

вывод: 

[2, 3, 5, 7, 11, 13, 17, 19]

для эффективного заправки поколение, вы можете использовать сито Эратосфена: 

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def _gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # 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

k=int(input())

def gen_primes(k):
    gp = _gen_primes()

    p = next(gp)
    while p < k:
        yield p
        p = next(gp)

res = list(gen_primes(k))
...