Простое число менее 501

Question

Я пытаюсь найти все простые числа больше 2 и меньше 501. Пожалуйста, обратитесь к моему коду, указанному ниже:

num = 501

x = int(input('Enter a number greater than 1: '))

if x > 1:
    for i in range(2, num):
        if x % i == 0:
            result = False
    else:
        result = True

    if result == True:
        print('Prime number.')
    else:
        print('Not a prime number.')
else:
    print('Not a prime number.')

Я пытался запустить код для двух чисел, 19 и 99Когда я ставлю «оператор прерывания» после кода, приведенного ниже, я получаю результат «99: не простое число», а «19, поскольку простое число печатается как не простое», и наоборот.

if x % i == 0:
        result = False
        break

Пожалуйста, исправьте приведенный выше код, чтобы напечатать правильный вывод.

Answer 1

Вместо использования пробного деления гораздо быстрее использовать Сито Эратосфена, изобретенное греческим математиком более двух тысяч лет назад:

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

Эта функция возвращает список простых чисел, меньших n , просеивание только по нечетным числам и обработка 2 отдельно.Если вы предпочитаете генерировать простые числа, а не возвращать список, используйте это:

def primegen(start=0): # stackoverflow.com/a/20660551
    if start <= 2: yield 2    # prime (!) the pump
    if start <= 3: yield 3    # prime (!) the pump
    ps = primegen()           # sieving primes
    p = next(ps) and next(ps) # first sieving prime
    q = p * p; D = {}         # initialization
    def add(m, s):            # insert multiple/stride
        while m in D: m += s  #   find unused multiple
        D[m] = s              #   save multiple/stride
    while q <= start:         # initialize multiples
        x = (start // p) * p  #   first multiple of p
        if x < start: x += p  #   must be >= start
        if x % 2 == 0: x += p #   ... and must be odd
        add(x, p+p)           #   insert in sieve
        p = next(ps)          #   next sieving prime
        q = p * p             #   ... and its square
    c = max(start-2, 3)       # first prime candidate
    if c % 2 == 0: c += 1     # candidate must be odd
    while True:               # infinite list
        c += 2                #   next odd candidate
        if c in D:            #   c is composite
            s = D.pop(c)      #     fetch stride
            add(c+s, s)       #     add next multiple
        elif c < q: yield c   #   c is prime; yield it
        else: # (c == q)      #   add p to sieve
            add(c+p+p, p+p)   #     insert in sieve
            p = next(ps)      #     next sieving prime
            q = p * p         #     ... and its square

О простых числах можно узнать на моем блоге .

Answer 2

Пожалуйста, исправьте приведенный выше код, чтобы напечатать правильный вывод.

Я считаю, что ниже приведена и упрощенная, и исправленная версия вашего кода:

number = int(input('Enter a number greater than 1: '))

if number > 1:
    for divisor in range(2, int(number ** 0.5) + 1):
        if number % divisor == 0:
            print('Not a prime number.')
            break
    else:  # no break
        print('Prime number.')
else:
    print('Not a prime number.')

Этот код работает, но не является оптимальным.Одна простая оптимизация состояла бы в том, чтобы обрабатывать 2 / даже в качестве особого случая и делить только на нечетные числа, начиная с 3. Значительная оптимизация состояла бы в том, чтобы переключиться на метод сита, как предлагает @ user448810.

Код, который вы предоставилитестирует только одно число на каждый ввод пользователя.Если вы хотите преобразовать его в цикл, который проверяет диапазон чисел, скажем, все числа больше 2, но меньше 501, то мы можем сделать:

for number in range(3, 501):

    if number > 1:
        for divisor in range(2, int(number ** 0.5) + 1):
            if number % divisor == 0:
                print(number, 'is not a prime number.')
                break
        else:  # no break
            print(number, 'is a prime number.')
    else:
        print(number, 'is not a prime number.')

Answer 3

Это будет работать:

import math   # This will import math module

def isprime(x):
    if x > 1:
        result = True
        for i in range(2, int(math.sqrt(x))+1 ):
            if ( x % i == 0):
                result = False
                break
        if ( result == True):
            print("Prime Number ")
        else:
            print("Not a Prime Number")

И вызов функции как:

 isprime(19)

Answer 4

Если я не ошибаюсь, это всегда будет возвращать false для всех чисел ниже 501, так как когда любое введенное число будет делиться само по себе. Вы также должны проверить, если x! = I.