Как найти простое число в питоне while

As a first exercise with Python, I’m trying to write a program using loops to find primes. Everything works with a for loop so I am trying to use a while loop. This works but the program returns a few incorrect numbers.

import math
# looking for all primes below this number
max_num = int(input("max number?: "))

primes = [2]  # start with 2
test_num = 3  # which means testing starts with 3

while test_num < max_num:
    i = 0
    # It's only necessary to check with the primes smaller than the square
    # root of the test_num
    while primes[i] < math.sqrt(test_num):
        # using modulo to figure out if test_num is prime or not
        if (test_num % primes[i]) == 0:
            test_num += 1
            break
        else:
            i += 1
    else:
        primes.append(test_num)
        test_num += 1

print(primes)

So the weird thing is that for max_num=100 it returns:

[2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

which is correct except for 9, 25 and 49 and I can’t figure out why.

1. Используйте простой метод итерации для определения простого числа в Python
2. Используйте функцию sympy.isprime(), чтобы проверить, является ли данное число простым числом в Python

Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.

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

Используйте простой метод итерации для определения простого числа в Python

В этом методе мы используем простой метод итерации с использованием цикла for или while. Переберите числа, начиная с 2 и далее до K/2, и проверьте, делит ли какое-либо из этих чисел K.

Если найдено число, соответствующее этому критерию, то возвращается False. С другой стороны, если все числа не соответствуют этому критерию, данное число K является простым числом, и возвращается значение True.

В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.

k = 13

# 1 not being a prime number, is ignored
if k > 1:
    for i in range(2, int(k/2)+1):
         if (k % i) == 0:
            print("It is not a prime number")
            break
    else:
        print("It is a prime number")

else:
    print("It is not a prime number")

Выход:

Вы можете оптимизировать приведенный выше код, применив некоторые изменения. Сделайте следующие оптимизации, чтобы сделать код еще быстрее:

• Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.

• Все простые числа существуют в форме 6n ± 1, за исключением 2 и 3. Следовательно, проверка делимости данного числа на 2 и 3, а затем проверка каждого числа, имеющего форму 6n ± 1, является более эффективным решением.

В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.

def isitPrime(k):
    if k==2 or k==3: return True
    if k%2==0 or k<2: return False
    for i in range(3, int(k**0.5)+1, 2):
        if k%i==0:
            return False

    return True
print(isitPrime(13))

Выход:

Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.

Используйте функцию sympy.isprime(), чтобы проверить, является ли данное число простым числом в Python

SymPy – это библиотека на Python, используемая для реализации символьной математики. Это упрощенная система компьютерной алгебры (CAS), которая содержит все основные функции. Для этого метода необходима установка этого модуля, и его можно загрузить, просто используя команду pip.

sympy.isprime() – это встроенная функция модуля SymPy, которую можно использовать для проверки возможных простых чисел. Это прямая функция, которая возвращает True, если проверяемое число простое, и False, если число не простое.

Следующий код использует функцию sympy.isprime(), чтобы проверить, является ли данное число простым числом в Python.

from sympy import *
  
isprime(8)
isprime(11)

Выход:

Следует отметить, что любое отрицательное число не подпадает под критерии простых чисел. Вывод этих функций может измениться, если ему сопоставить какое-либо отрицательное число.